GATE CS 1994 Q1.7 — Asymptotic Worst Case Time and Space Complexity

In Binary Search, we search for a target element in a sorted array of size $n$ as follows:

1. Compare the target element with the middle element of the current search space. This step takes constant time, say $k$ (where $k$ is a constant).
2. If the target is not found at the middle, we discard one half of the array and recursively search in the remaining half of size $\frac{n}{2}$.

Since we only make one recursive call on a subproblem of half the size, the recurrence relation is:

where $k$ is a constant representing the time taken for the comparison and division steps.

Solving this recurrence using Master's Theorem or iterative substitution yields:

Thus, Option B is the correct recurrence relation.