Which one of the following recurrence relations best represents the time complexity of the binary search algorithm running on an ordered array of $n$ elements?

Question

In a binary tree, what is the maximum number of nodes at level k?

Answer 1

Step 1: Each call in binary search halves the array size and does only a constant amount of comparison work, so the recursion tree has one branch per level (not two), with constant work added at each level.
Step 2: The array size shrinks from n to 1 after about $\log_2 n$ levels of halving.
Step 3: Total work is the constant work per level times the number of levels.
\[ T(n) = \boxed{T(n/2) + 1}, \quad \text{giving } T(n) = O(\log n) \]

Answer 2

A third way is to unroll the recurrence $T(n) = T(n/2) + 1$ directly by substitution and check the resulting closed-form expression, then compare that to what the other candidate recurrences would give for the same problem size.

Unrolling: $T(n) = T(n/2) + 1 = [T(n/4)+1]+1 = T(n/4)+2 = T(n/8)+3 = \cdots = T(n/2^k) + k$. The recursion bottoms out when $n/2^k = 1$, i.e. $k = \log_2 n$, giving $T(n) = T(1) + \log_2 n$, a value that grows very slowly (for example, only about 10 steps for n=1024), matching the well-known fast behavior of binary search in practice.

T(n) = T(n/2) + n: Unrolling this instead gives $T(n) = n + n/2 + n/4 + \cdots \approx 2n$, a total that grows proportionally with n itself, not just its logarithm — for n=1024 this would mean roughly 2000 steps, far more than binary search actually takes.
T(n) = 2T(n) + 1: This does not shrink the problem at all between calls, so unrolling it does not even terminate in a finite closed form, ruling it out entirely as a model for any real algorithm.
T(n) = 2T(n/2) + n: Unrolling this gives $T(n) = n + n + n + \cdots$ over $\log_2 n$ levels, i.e. $T(n) \approx n\log_2 n$ — for n=1024 this is roughly 10000 steps, again far more than the small number of steps binary search actually takes.
T(n) = T(n/2) + 1: The unrolled result above, $T(1)+\log_2 n$, gives a very small number of steps for large n (about 10 for n=1024), matching the actual fast, logarithmic-time behavior of binary search closely.

Directly unrolling the recurrence and comparing the resulting step count to binary search's known fast performance confirms the matching recurrence.

Therefore, the correct answer is T(n) = T(n/2) + 1.

Answer 3

A third way is to unroll the recurrence $T(n) = T(n/2) + 1$ directly by substitution and check the resulting closed-form expression, then compare that to what the other candidate recurrences would give for the same problem size.

Unrolling: $T(n) = T(n/2) + 1 = [T(n/4)+1]+1 = T(n/4)+2 = T(n/8)+3 = \cdots = T(n/2^k) + k$. The recursion bottoms out when $n/2^k = 1$, i.e. $k = \log_2 n$, giving $T(n) = T(1) + \log_2 n$, a value that grows very slowly (for example, only about 10 steps for n=1024), matching the well-known fast behavior of binary search in practice.

T(n) = T(n/2) + n: Unrolling this instead gives $T(n) = n + n/2 + n/4 + \cdots \approx 2n$, a total that grows proportionally with n itself, not just its logarithm — for n=1024 this would mean roughly 2000 steps, far more than binary search actually takes.
T(n) = 2T(n) + 1: This does not shrink the problem at all between calls, so unrolling it does not even terminate in a finite closed form, ruling it out entirely as a model for any real algorithm.
T(n) = 2T(n/2) + n: Unrolling this gives $T(n) = n + n + n + \cdots$ over $\log_2 n$ levels, i.e. $T(n) \approx n\log_2 n$ — for n=1024 this is roughly 10000 steps, again far more than the small number of steps binary search actually takes.
T(n) = T(n/2) + 1: The unrolled result above, $T(1)+\log_2 n$, gives a very small number of steps for large n (about 10 for n=1024), matching the actual fast, logarithmic-time behavior of binary search closely.

Directly unrolling the recurrence and comparing the resulting step count to binary search's known fast performance confirms the matching recurrence.

Therefore, the correct answer is T(n) = T(n/2) + 1.

Which one of the following recurrence relations best represents the time complexity of the binary search algorithm running on an ordered array of $n$ elements?

Show Hint

The Correct Option is D

Approach Solution - 1

Approach Solution -2

Top Questions on Data Structures

Questions Asked in OJEE exam