Why We Measure Growth, Not Speed
You'll learn to
- -Explain what Big-O actually measures - growth rate, not wall-clock speed
- -Understand why algorithm choice eventually beats hardware, no matter how fast the hardware is
- -Recognize the difference between code that "runs fast on my machine" and code that scales
Everything up to this point in the course has been about writing correct Python - the right syntax, the right data structure, the right abstraction. Starting here, a second question enters the picture: how does this code behave as the input grows? A function that works perfectly on ten items can quietly become unusable on ten million, and the ability to predict that in advance - without running it - is one of the most interview-tested skills in this entire tier.
Two Programs, Same Answer, Very Different Futures
Consider two ways of answering the same question: does this list contain any duplicate values? The first checks every pair of elements directly. The second remembers every value it has already seen.
On a list of ten items, both functions feel instant - the difference is invisible on a stopwatch. That is exactly the trap: timing small inputs reveals almost nothing about how a piece of code will behave once the input is large, and large is where real systems live.
What "Big-O" Actually Describes
Big-O notation describes how the number of operations a piece of code performs grows as the input size, conventionally called n, grows - not how many seconds it takes on any particular machine. It deliberately ignores constant factors and hardware speed, because those change from machine to machine and year to year, while the underlying growth pattern of an algorithm never does. This is why a slow computer running an O(n) algorithm will always eventually beat a fast computer running an O(n²) algorithm, once n is large enough - the fast computer only wins the early rounds.
That last row is the whole point of this chapter: at n = 1,000,000 the naive version is roughly a million times slower than the fast one, using the exact same CPU. No amount of hardware upgrades closes a gap caused by the algorithm's shape rather than its execution speed.
Why does a nested loop over the input worry an interviewer?
"It looks messy and hard to read."
"Nested loops over the same input typically mean O(n squared) work, which degrades badly as n grows - I would look for a way to trade a small amount of extra memory, like a set or a dict, for a single pass instead."
- -Big-O measures growth rate as input size increases, not raw speed on any one machine.
- -Constant factors and hardware are deliberately ignored - what matters is the shape of the curve, not where it starts.
- -A better algorithm on slow hardware eventually beats a worse algorithm on fast hardware - there is always a large-enough n where this becomes true.