Which of the following is the correct recurrence relation related to the…

Key idea: Binary search halves the search space each step and does only constant work (a few comparisons) at each step.

• One recursive call on n/2

• Plus constant-time work (comparison), i.e., Θ(1)

• Base case: T(1) = Θ(1)

Therefore the recurrence is:

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

Quick derivation by unfolding:

• T(n) = T(n/2) + 1 = T(n/4) + 2 = ... = T(n/2^k) + k

• Stop when n/2^k = 1, so k = log2 n. Hence T(n) = T(1) + log2 n = Θ(log n).

Master theorem confirmation:

• a = 1, b = 2 so n^{log_b a} = n^0 = 1; f(n) = Θ(1). This matches the case that yields Θ(log n).

Conclusion: The correct recurrence for binary search is T(n) = T(n/2) + Θ(1), which solves to Θ(log n).

Why the other recurrences are not appropriate:

• T(n) = T(n/2) + O(n): Implies linear extra work per level, not constant, so it does not describe binary search.

• T(n) = 2T(n/2) + O(n): Describes algorithms that recurse on both halves and do linear merging work (e.g., mergesort), giving higher complexity.

• T(n) = 2T(n/2) + 1: Two recursive calls process both halves and lead to Θ(n) overall, not the logarithmic behavior of binary search.