Self-doubt

Question

Which of the following is exact recurrence relation for binary search (in terms of number of comparisons) ?

1. T(n) = 2T(n/2) + 1

2. T(n) = 2T(n/2) + 2

Please specify relevant reasons.

Answer 1

Both are wrong. It is $T(n) = T(n/2) + \theta(1)$

What is 1 or 2 there? It's unit? Actually that is computational cost of finding mid in binary search which you can't write as 1 or 2. You should use $\theta(1)$ to denote it is equal to any constant not just 1 or 2.  Set your equation accordingly.

Comments

So there will be 2 comparisons in all right ?

---

yes, in exact it will be 2 comparisons,

---

No. Of comparisons is T(n/2)+1

n/2 for for recursive half + 1 for comparison with mid

tell me if I am wrong

Answer 2

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

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

T(N/2) = T(N/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:

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)

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

T(N) =  1 + LogN

Therefore the running time of binary search is:

T(N) = O(LogN)

Answer 3

Recurrence relation is T(n) = T(n/2) + 1, where T(n) is the time required for binary search in an array of size n.

T(n) = T( n 2k )+1+ ··· + 1 Page 2 Since T(1) = 1

 when n = 2k, T(n) = T(1) + k = 1 + log2(n).