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$.