Why halving means O(log n)
Binary search throws away half the remaining items each step. The question "how slow is it?" becomes "how many times can you halve n before you reach 1?" — and that count is log₂(n).
| n | 16 | 1,024 | 10⁶ | 10⁹ |
|---|---|---|---|---|
| steps | 4 | 10 | 20 | 30 |