1. The problem
You want to find "Smirnov" in a paper phone book with a million names. The names in it are in alphabetical order. There are two ways to do it:
- Flip page by page from the start until you reach the name.
- Open the book in the middle and check whether you went past the right letter or haven't reached it yet. Throw away the half that can't hold the name. Then do the same with the half that is left.
Both ways find Smirnov. The first takes a long time. The second takes a few seconds. Same answer, very different cost.
2. Count the work, not the seconds
You measure how fast a way is by counting steps: how many boxes you look at. Seconds are no good for this. On a fast computer the slow way only becomes a little less slow.
Flipping looks at up to a million pages. Halving looks at about twenty. After the first look 500,000 pages are left, after the second 250,000, after the third 125,000. Each look throws away half of what is left. After about twenty such steps one page is left.
3. The gap explodes as things grow
On a small list nobody notices a difference: both ways finish instantly. The difference shows up only when there is a lot of data. Then it is huge:
| names | one by one | halving |
|---|---|---|
| 1,000 | ~1,000 | ~10 |
| 1,000,000 | ~1,000,000 | ~20 |
| 1,000,000,000 | ~1,000,000,000 | ~30 |
The slow way grows as fast as the data. The fast way barely grows: when there are a thousand times more names, it needs only 10 more steps. This difference is why people study algorithms at all.
4. Your turn (no code)
A website search goes through the products one by one. With 100 products it feels instant. With 5,000,000 it freezes. The code did not change. So what did? And which of the two ways above would fix it?
Answer: the data grew. Going one by one slows down by the same factor as the data grew. Halving stays fast at any size, but it needs the data sorted in advance. Picking the right way before the data grows is the programmer's job.
5. Takeaway
Some ways stay cheap as the data grows. Others fall apart. You just saw, on your own and with no math, the two most important kinds of growth: "look at everything" and "halve each time". In the next lesson they get their real names, and Big-O appears. After that, every pattern in the course teaches you to stay on the cheap side of this table.
On LeetCode
No LeetCode problem here, because this lesson counts steps and writes no code. It explains why every LeetCode problem prints limits like n ≤ 10^5, and lesson 9 turns those limits into a choice of method.
Reading as a guest
Every free lesson is open to read and run. A free account marks lessons done and shows where you are in the course.