Question

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?

• A. $T(n) = T(n/2) + n$
• B. $T(n) = 2T(n) + 1$
• C. $T(n) = 2T(n/2) + n$
• D. $T(n) = T(n/2) + 1$

Hint:

Whenever an algorithm divides the problem into half and does constant work at each step, its recurrence is usually of the form $T(n)=T(n/2)+c$.

Answer 1

The Correct Option is D

Step 1: Understanding binary search.
Binary search works by comparing the target element with the middle element of the sorted array. Based on this comparison, the algorithm discards half of the array and continues searching in the remaining half.
Step 2: Analyzing the work done at each step.
At each step, the size of the problem reduces from $n$ to $n/2$. Apart from this reduction, only a constant amount of work is done for comparison.
Step 3: Forming the recurrence relation.
Since the problem size is halved and only constant time is spent at each level, the recurrence relation is: \[ T(n) = T(n/2) + 1 \]
Step 4: Final conclusion.
Therefore, the correct recurrence relation representing binary search is $T(n) = T(n/2) + 1$.

Answer 2

Another way to identify the correct recurrence is to solve each of the four candidate recurrences using the Master theorem (or simple pattern recognition) and check which one produces the well-known \(O(\log n)\) time complexity of binary search.

1. T(n) = T(n/2) + n: Here a=1, b=2, and the extra work per level is n (not constant), which by the Master theorem resolves to \(O(n)\) overall — this is the complexity of a linear scan, not binary search, so it does not match.
2. T(n) = 2T(n) + 1: This recurrence does not even reduce the problem size at all (it calls T(n) itself, not T(n/2)), which does not correspond to any divide-and-conquer algorithm that terminates in finite time, let alone binary search.
3. T(n) = 2T(n/2) + n: Here a=2, b=2 with linear extra work per level, which by the Master theorem resolves to \(O(n\log n)\) — this is the classic complexity of algorithms like merge sort, not binary search.
4. T(n) = T(n/2) + 1: Here a=1, b=2 with only constant extra work per level, which by the Master theorem resolves to \(O(\log n)\) — exactly the well-known time complexity of binary search.

Solving each recurrence and comparing its result against binary search's known \(O(\log n)\) complexity leaves only one recurrence that matches.

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