Why a cost language exists
You now own containers that make competing speed claims, and the next unit will make more ("map is slower than unordered_map, but both beat scanning a vector"). To compare algorithms you need a measure that does not depend on whose laptop ran the test — a 10-year-old machine and a new one differ by a constant factor, but the shape of an algorithm's cost curve is the same everywhere. Big-O notation is that measure, it is how every interviewer will ask you about your solution ("what's the complexity?"), and it is how library documentation states its guarantees.
The definition: big-O describes how an algorithm's running time (or memory) grows as the input size n grows, keeping only the dominant term and ignoring constant factors. "This algorithm is O(n)" means: double the input, and the work roughly doubles. O(n²) means: double the input, and the work roughly quadruples.
The classes you will actually use, each anchored to something you have already written:
| Class | Name | Growth when n doubles | You have seen it as |
|---|---|---|---|
| O(1) | constant | unchanged | v[i], push_back |
| O(log n) | logarithmic | +1 step | halving n until 1 |
| O(n) | linear | ×2 | one loop over the input |
| O(n log n) | linearithmic | a bit over ×2 | sorting (next lesson) |
| O(n²) | quadratic | ×4 | nested loops over all pairs |
Why O(log n) means "halving": a logarithm answers "how many times can I cut n in half before reaching 1?" For n = 1,000,000 the answer is only about 20 — which is why searching a sorted structure by repeated halving crushes scanning element by element.
Code exercise · cpp
Run the comparison: worst-case steps to find a value among 1,000,000 by scanning (linear, O(n)) versus by repeatedly halving a sorted range (binary search, O(log n)).
Reading big-O off your own code
Three mechanical rules cover most code you will write:
- A loop over n items is O(n). A loop inside a loop multiplies: two nested loops over the input (lesson 3-3's pattern with both bounds at n) run the body n × n times — O(n²).
- Sequential steps add, and the biggest term wins. An O(n) pass followed by an O(n²) pass is O(n + n²) = O(n²). For n = 1,000,000, the n² part is a trillion operations while the n part is a millionth of that — the small term is rounding error, which is exactly why big-O discards it.
- Constants are dropped. Looping over the input three times is O(3n) = O(n). The 3 matters to a profiler, but it does not change the curve's shape, and the shape is what decides whether your solution finishes at all.
The rule of thumb that makes this practical: a judged environment executes very roughly 10⁸ simple operations per second. So for n = 100,000, an O(n²) solution needs ~10¹⁰ operations — minutes, an automatic time-limit failure — while O(n log n) needs ~1.7 × 10⁶: milliseconds. Estimating this before coding is precisely what interviewers mean by "discuss complexity first."
Code exercise · cpp
Your turn: run the growth table for n vs n*n. Notice the O(n) column growing 10x per row while the O(n²) column grows 100x — that widening gap is everything big-O is about.
Quiz
A function loops over a vector of n elements once, and inside that loop does a constant-time map lookup. Then, separately, it loops over the vector once more to print results. What is its overall time complexity?