Big-O answers one question: when the input gets 10× bigger, how much more work does the code do? Not seconds, not milliseconds. The shape of the growth. Play with each idea below, then train in the gym until reading complexity off code feels automatic.
At small n every algorithm looks fast. Drag the size up and see which curves leave the chart. Switch to log scale to see the slower-growing ones again.
| class | operations | time @10⁸/s |
|---|
Pick a snippet and run it. Every line keeps a hit counter. The innermost line (amber) is the work, and its count as n grows is the complexity.
Each dot is the real count of the work line for that n. The line is the predicted class scaled by a constant c. Big-O drops c.
Real step counts look like 3n² + 40n + 900. Big-O keeps only the part that wins at scale. Change the coefficients and watch the biggest term take over anyway.
Searching for something might end on step one. Big-O plans for when it is the last item, or not there at all.
Two passes, half a pass, ten passes: they all grow linearly. O(2n) and O(n/2) are both O(n).
In n² + n, the n becomes noise once n is big. Keep the fastest-growing term.
A loop that runs a fixed number of times (26 letters, 4 directions) is a constant, even if it is nested.
Two arrays are not both "n". One after the other adds, nested multiplies. You can't simplify a + b any further.
The input limits in a problem statement tell you which complexity the intended solution has. Most judges give about 1 second, and a typical machine does about 10⁸ simple operations per second. Pick an n to see what still fits.
Vertical tick = the 10⁸ budget. Constants matter near the edge: “borderline” means it might pass with tight code.
| n up to | aim for | usually means |
|---|
A divide-and-conquer function that makes a calls on pieces of size n/b and does nd work of its own costs T(n) = a·T(n/b) + nd. Add up the work level by level. Whichever end of the tree is heaviest wins: the root, the leaves, or every level equally.
Left: subproblems per level (size inside). Right: total work on that level. Red = heaviest level.
fib(n-1) + fib(n-2) shrinks by one, so the tree is n levels deep and doubles each level: O(2ⁿ). Run it in lab 02.When a dynamic array (Python list, Java ArrayList, C++ vector) is full, it copies everything into a bigger block. That push costs O(n), but if capacity doubles, the copies are rare enough that the average stays O(1). Grow by a fixed amount instead and the average climbs with n.
f(n) is O(g(n)) if some constant c makes c·g(n) stay above f(n) for every n past some point n₀. Ω is the same idea from below, and Θ means both at once. Try to find a c that works.
Average case unless a worst case is shown in grey. Built-ins are where hidden costs live, so check the last tab.
Read the code, type the time and space complexity, and see what trips you up. Answers are checked by meaning, not by spelling: n log n, nlogn and n*log(n) all count. Unsimplified answers like O(2n) are marked almost.
Accuracy by category over your attempts. Red marks your weakest area, and Practice deals more of it.