Binary Search Complexity: Why It Is $O(\log n)$ (Not $O(n)$, $O(n^2)$, or $O(n\log n)$)

Binary search (Binary search ) has time complexity that grows logarithmically with input size: $O(\log n)$ in the average and worst cases.2 This makes the correct option among:

• (i) $O(n)$
• (ii) $O(\log n)$
• (iii) $O(n^2)$
• (iv) $O(n\log n)$

✅ Correct answer: (ii) $O(\log n)$.2

Key idea: halving the search space

Each iteration of binary search compares the target to the middle element and then keeps only one half of the remaining interval. After $k$ iterations, the remaining number of candidates is: $\frac{n}{2^k}$ We stop when the interval size becomes 1: $\frac{n}{2^k} = 1 \Rightarrow 2^k = n \Rightarrow k = \log_2(n)$ So the number of comparisons (and thus runtime) scales as $O(\log n)$. This matches standard complexity analyses of binary search.2