Binary Search Complexity: Why the Correct Choice is $O(\log n)$

Binary search works on a sorted array by repeatedly comparing the target to the middle element and discarding half of the remaining search interval each step. This halving implies that the number of iterations (and thus the running time in the worst case) grows proportionally to a logarithm in $n$, giving time complexity $O(\log n)$.2

Answer to the multiple-choice question: (ii) $O(\log n)$.

Key notions to keep straight: binary search; time complexity; worst-case; logarithmic.

Matching the options

Because binary search’s interval size shrinks by a factor of 2 each step, the worst-case number of iterations is logarithmic in $n$.2 Therefore:

• (i) $O(n)$ — incorrect (that would correspond to checking one element per step, like linear search).
• (ii) $O(\log n)$ — correct.
• (iii) $O(n^2)$ — incorrect (quadratic time would require something like nested loops over $n$).
• (iv) $O(n \log n)$ — incorrect (that growth typically comes from combining linear work across $\\log n$ levels, e.g., merge sort, not from halving a single search interval).

To contrast, linear search has worst-case time $O(n)$, while binary search on sorted data has time $O(\log n)$.