Big-O Notation and Orders of Growth
Describing how the work an algorithm does grows with the size of its input, keeping only the term that dominates and dropping constants. It gives O(1), O(log n), O(n), O(n log n) and O(n squared) as a way to compare methods at any scale.
What a learner can do afterwards
- Turn an operation count such as 3n + 7 into its big-O form and say what was dropped and why
- Put O(1), O(log n), O(n), O(n log n) and O(n squared) in order of growth
- Predict what happens to the work when the input doubles, for each of those orders
1 · Read
Big-O notation keeps only the shape of the growth and throws away the details, to compare methods on a huge class list. Turn 3n + 7 into O(n): drop the 7 and drop the 3, because for large inputs the n term decides everything. Constants reflect the machine and coding details, not the algorithm, and they stop mattering beside growth as n gets large.
Five orders cover most methods you meet. From slowest to fastest growth: O(1) stays flat, then O(log n), then O(n), then O(n log n), then O(n squared). Linear search grows in step with the list while binary search barely notices it getting longer, which is why one is O(n) and the other O(log n).
Predict doubling to feel each shape. If the input doubles, O(1) work stays flat, O(log n) needs about one extra step, O(n) work doubles too, and O(n squared) roughly quadruples since doubling n multiplies n squared by four. Saying binary search is O(log n) promises its work never grows faster than a logarithmic curve.
Big-O promises an upper bound on growth: the work never grows faster than the named curve for large n. That promise is what lets you compare algorithms fairly at any scale. Big-O summarises an operation count, so there must be a count to summarise before the notation means anything.
Drop the constants, name the shape, predict the doubling.
2 · Watch
Take it off screen
Where it sits
Learn first
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.