The power of halving
There is one more growth family you will meet constantly: O(log n), logarithmic time. It shows up whenever each step throws away half of what is left.
Think of the number-guessing game. I pick a number from 1 to 1000, you guess 500, I say "higher", and instantly 500 possibilities are gone. Each guess halves the range.
log₂ n just answers: how many times can you halve n before you reach 1? No other math needed. Let's count halvings directly.
Code exercise · python
Run this. A million items collapse to 1 in only 19 halvings. That number, the halving count, is log₂ n rounded down.
Binary search: halving in action
If a list is sorted, you can search it the guessing-game way. Look at the middle item. Too small? The target must be in the right half. Too big? Left half. Either way, half the list is eliminated per check.
That is binary search: O(log n) instead of the O(n) scan from lesson 1-1. The gap is absurd at scale:
| n | O(log n) checks | O(n) checks | O(n²) steps |
|---|---|---|---|
| 1,000 | ~10 | 1,000 | 1,000,000 |
| 1,000,000 | ~20 | 1,000,000 | 10¹² |
The catch: the data must already be sorted, and you need instant access to the middle item. Keep that second requirement in mind, it will decide arrays vs linked lists in unit 4.
Code exercise · python
Your turn: implement binary search over a sorted list, counting comparisons. Keep `lo` and `hi` indexes, look at the middle, and shrink the side that cannot contain the target. Return `(index, checks)`, or `(-1, checks)` if the target is missing.
Quiz
Binary search needs about 20 checks for 1,000,000 sorted items. About how many for 2,000,000?
Where halving shows up this week
O(log n) is not an interview curiosity; it is load-bearing infrastructure you will touch as a working engineer:
git bisectfinds the commit that broke your build by binary-searching the commit history: 1,000 suspect commits take about 10 test runs, not 1,000.- Database indexes answer
WHERE id = 7423by walking a balanced search tree instead of scanning the table — the halving idea grown into a structure, which you will build in unit 7. - Python's
bisectmodule binary-searches any sorted list for you, so you rarely hand-write the loop outside of interviews.
The common thread: someone paid once to keep data sorted (or tree-shaped) so that every later question costs log n instead of n.
Problem
Rank these from fastest-growing to slowest-growing for large n: O(n), O(1), O(n²), O(log n). Give your answer as the fastest-growing one (the worst for large inputs).