Growth Rate Beats Raw Timing
What This Concept Is
Big O notation is a way to describe how the amount of work grows as the input gets bigger. It is not a stopwatch. It is a growth-rate lens that helps you compare algorithms before inputs become painful.
Why It Matters Here
Early learners often ask, "Which algorithm is faster?" The better question is, "How does this choice scale?" An algorithm that feels acceptable on 100 items can become absurd on 1 billion items if its growth is bad.
Concrete Example
Simple search on a list of size n may need to inspect every item, so it grows like O(n).
Binary search on a sorted list of size n cuts the possibilities in half each step, so it grows like O(log n).
That difference looks small on tiny inputs. It becomes huge on big ones:
| Input size | Simple search | Binary search |
|---|---|---|
| 128 items | up to 128 checks | up to 7 checks |
| 1,024 items | up to 1,024 checks | up to 10 checks |
| 1,000,000,000 items | up to 1,000,000,000 checks | about 30 checks |
Common Confusion / Misconception
Big O does not tell you exact runtime in seconds, and it does not tell you everything that matters about performance. It intentionally compresses the picture so you can compare growth. Another common mistake is treating one lucky run as the algorithm's real story. In this module, use Big O mainly as a worst-case growth lens.
How To Use It
Use Big O to compare the dominant shape of work:
O(1)stays flat as input growsO(log n)grows slowlyO(n)grows in direct proportionO(n log n)is common for efficient sortingO(n^2)usually means pairwise or repeated comparisons that get expensive quickly
When choosing between two approaches, ask what happens when the input becomes 10x or 100x larger.
Check Yourself
- Why is
O(log n)a different kind of improvement from "5 ms faster on my laptop"? - Which grows more dangerously as input scales:
O(n log n)orO(n^2)? - Why can two algorithms both feel fine on tiny inputs but diverge badly later?
Mini Drill or Application
Match each situation to the most likely growth pattern and explain why:
- reading every item in a list once
- looking up a value in a well-behaved hash table
- sorting a large list with a fast comparison sort
- comparing every pair of students in a class
Then write one short paragraph answering this: if an algorithm feels fast on 100 items, why can that still be misleading?