I understand most of it apart from telescoping par, Please explain telescoping i

Question

I understand most of it apart from telescoping par, Please explain telescoping in details how it works.

Problem 2: Binary search in a sorted array Algorithm Search (E) in array[1..N]: Compare E with the middle element. If equal : stop with success If E is greater, search E in array [N/2+1 .. N] Otherwise, search E in array[1 .. N/2] Initial condition: the time to search in an array of 1 element is constant: Recurrence relation: The time to search in an array of N elements is equal to the time to search in an array of N/2 elements plus 1 comparison. T(N) = T(N/2) + 1 Next we perform telescoping: re-writing the recurrence relation for N/2, N/4,, 2 TON) T(N/2) + 1 TN/2) TON/4) +1 T(N/4) = T(N/8) + 1 T(4) T(2)+1 T(2) T(1)+ 1 Next we sum up the left and the right sides of the equations above: TN) + T(N/2) TN/4)+ T(N/8) +.. +T(2) The number of 1's on the right side is LogN Finally, we cross the equal terms on the opposite sides and simplify the remaining sum on the right side: T(N) = T(1) + LogN TN) 1 +LogN Therefore the running time of binary search is: TN) O(LogN)

Explanation / Answer

Hey,

Below is the answer to your question

Given,

T(N/20)=T(N/2)+1

the above equation can be written as

T(N)=T(N/21)+1---------------eq1

Lets replace N by N/2

So, T(N/2)=T(N/4)+1

the above equation can be written as

T(N/21)=T(N/22)+1---------------eq2

Again replace N by N/2

So, T(N/4)=T(N/8)+1

the above equation can be written as

T(N/22)=T(N/23)+1---------------eq3

The process will continue till h equations

So, equation h is

T(N/2h-1)=T(N/2h)+1---------------eqh

The base of this recursion formula is

T(2)=T(1)+1

compare right hand side of eqh and above equation

So, N/2h=1

So, h=log2(N)

This shows that total number of iterations till T(1) is h=log2(N)

So, adding all equations left and right hand side

T(N)+T(N/2)+T(N/4)+T(N/8)...........................+T(2)=T(N/2)+T(N/4)+T(N/8)+................T(2)+T(1)+(1+1+1......+1)(h times)

on left hand and right hand side T(N/2),T(N/4),T(N/8)...........T(2) will cut each other

So,

T(N)=T(1)+h

Therefore T(N)=O(h)

but h=log2(N)

So, T(N)=O(log2(N))

Kindly revert for any queries, will be waiting for your positive feedback.:)

Thanks.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---