What is the worst-case number of arithmetic operations performed by recursive…
2021
What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size \(n\) ?
- A.
\(\theta (\sqrt n)\) - B.
\(\theta (log_2 (n))\) - C.
\(\theta (n^2)\) - D.
\(\theta (n)\)
Attempted by 238 students.
Show answer & explanation
Correct answer: B
Key idea: each recursive call halves the remaining array and does a constant amount of work.
Recurrence: T(n) = T(n/2) + Θ(1), because each call computes the middle index and performs a comparison (constant work) and then recurses on half the array.
Unroll: after k calls the remaining size is n/2^k. Stop when n/2^k ≤ 1, which gives k = ⌈log_2 n⌉.
Conclusion: T(n) = Θ(k) = Θ(log_2 n).
Therefore, the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size n is Θ(log_2 n).
A video solution is available for this question — log in and enroll to watch it.