Common complexities — O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!): Visual walkthrough

Before line one, four words we will use constantly:

Everything below is one long answer to: "as n grows, which shapes pull ahead, and why?"

Step 1 — The board: n on the floor, steps up the wall

WHAT. We set up the one arena every class lives in. The horizontal axis (the floor) is n, the input size. The vertical axis (the wall) is $T (n)$ , the number of steps. Every algorithm is a curve climbing this wall as we walk right along the floor.

WHY. To compare growth we need them on the same picture. "Faster-growing" then simply means "the curve that ends up higher for large n". No formula yet — just a stage.

PICTURE. Look at figure s01: a flat line hugging the floor (that will become $O (1)$ ) and a steep line rocketing up the wall. The eye already ranks them — that ranking is complexity.

Figure — Common complexities — O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ), O(n!)

Step 2 — O(1): the flat floor (no dependence on n)

WHAT. The simplest curve: a horizontal line. Grabbing arr[i] or stack.push() touches a fixed number of things regardless of how big the list is.

WHY THIS SHAPE. There is no loop over the data. Write the step count: $T (n) = a fixed number of steps c$ The symbol c is a constant — it does not contain n anywhere. A quantity with no n in it cannot change when n changes. So the curve is dead flat.

PICTURE. Figure s02 draws $T (n) = c$ as a level chalk line. As we slide right along n, the height never moves — that flatness is the visual signature of constant time.

Recall Why "constant" and not "1"?

The 1 in $O (1)$ is a placeholder for "some fixed number", not literally one step. Whether it's 1 step or 1000 steps, if that number never grows with n, it's $O (1)$ — the tight estimate erases the exact value.

Step 3 — O(log n): halving the pile (dividing, never subtracting)

WHAT. Start with n items. Each step throws away half of what's left. How many steps until one item remains? That count is the height of the log curve.

WHY A LOG. First, name the thing we are counting: let k be the number of halvings (i.e. the number of steps) we perform. Now follow the pile size step by step — this is the derivation, drawn:

n \div2 \frac{n}{2} \div2 \frac{n}{4} \div2 \dots \div2 \frac{n}{2 ^{k}}

The exponent on the 2 counts how many cuts we have made, so after k cuts the pile is $n / 2^{k}$ . We stop when the pile is a single item:

pile size after k cuts \frac{n}{2 ^{k}} = one item left 1 \Rightarrow 2^{k} = n \Rightarrow k = "how many times can I halve n ?" lo g_{2} n

WHY the tool $lo g_{2}$ and not division or subtraction? We ask "2 raised to what power gives n?" — that question is the definition of $lo g_{2} n$ . We reach for a log precisely because the process multiplies the shrink factor (÷2, ÷2, ÷2…) rather than removing a fixed amount each time. If we instead subtracted a constant each step, we'd get $O (n)$ — the log is the fingerprint of dividing by a constant factor.

PICTURE. Figure s03 shows the pile as a bar being sliced in half over and over; the step counter on the side climbs by 1 every time the bar halves — so a million-item pile needs only ~20 slices. That brutal shrinking is why Binary-Search is so cheap.

Step 4 — O(n): one glance per item (the straight ramp)

WHAT. Do a fixed chunk of work once for every element: find the max, sum a list, scan for a value.

WHY LINEAR. One pass, one visit each:

T (n) = steps per item c \times number of items n = c n

Because n appears to the first power, doubling the input doubles the work — a perfectly straight ramp. This is the honest, "read everything once" cost, and it's the baseline every efficient algorithm is measured against.

PICTURE. Figure s04 lines up n boxes and a single arrow sweeping across them left to right, ticking the step counter once per box. Straight line, constant slope.

Step 5 — O(n log n): a stack of linear passes (the recursion tree)

WHAT. Split the data into halves, sort each half, then merge them back in one linear sweep. This is Merge-Sort. Its cost is described by a recurrence — a formula defining $T (n)$ in terms of smaller T.

WHY this shape — build it from the tree. The recurrence is:

T (n) = two halves 2 cost of one half T (n /2) + merge = one linear sweep c n

Draw it as a tree (why a tree? because each split spawns two children, exactly like branching):

Depth of the tree = how many times we can halve n before hitting size 1 → that's $lo g_{2} n$ levels (we already earned this number k in Step 3!).
Work on each level = at level 0 there is one piece of size n costing $c n$ ; at level 1, two pieces of size $n /2$ costing $2 \cdot c \frac{n}{2} = c n$ ; at level 2, four pieces of size $n /4$ costing $4 \cdot c \frac{n}{4} = c n$ ; and so on. Every level costs exactly $c n$ because the pieces always add back up to n.

Now why multiply — because total cost is the sum over levels, and every term in that sum is the same $c n$ :

T (n) = add up each level’s work level = 0 \sum l o g_{2} n - 1 c n = l o g_{2} n equal terms c n + c n + \dots + c n = per level c n \times number of levels lo g_{2} n = O (n lo g n)

Adding the same value $lo g_{2} n$ times is multiplication — that is exactly why "work-per-level × number-of-levels" is legitimate here.

PICTURE. Figure s05 draws the recursion tree: each row labelled with its total work $c n$ on the right, the number of rows braced as $lo g_{2} n$ on the left. The sum "rows × work-per-row" is the whole cost — see it as the area of the tree. (The formal machinery behind this is Recurrence-Relations and the Master-Theorem.)

Step 6 — O(n²): everyone meets everyone (the filled square)

WHAT. For each element, do work proportional to all elements — a loop inside a loop.

WHY QUADRATIC. Count the pairs. The n×n grid of "element i talks to element j" has:

T (n) = outer loop n \times inner loop n = n^{2}

Even the triangular version (inner loop starts at i) gives:

i = 1 \sum n i = filled half-square \frac{n ( n + 1 )}{2} = \frac{n ^{2}}{2} + \frac{n}{2}

The tight estimate keeps the biggest term and drops the constant $\frac{1}{2}$ and the lone $\frac{n}{2}$ , leaving $O (n^{2})$ — the half-square grows in the same shape as the full square.

PICTURE. Figure s06 shades the full n×n grid (all pairs) and, over it, the triangular half. Same parabolic growth — the eye sees the shaded area balloon as n widens.

Step 7 — O(n³): a loop inside a loop inside a loop (the solid cube)

WHAT. Three nested loops, each running n times — the classic being naive multiplication of two n×n matrices: for each output cell (i, j) you sum over a running index k.

WHY CUBIC. Count how the loops multiply, one nesting at a time:

T (n) = outer loop i n \times middle loop j n \times inner loop k n = n^{3}

Each loop is inside the previous, so their counts multiply (Step 6's rule, applied twice). Where Step 6 filled a flat n×n square of work, here you fill a solid n×n×n cube: one unit of work for every triple $(i, j, k)$ .

PICTURE. Figure s07 stacks the flat square of Step 6 into a solid cube of side n; the number of little unit cells inside is $n^{3}$ , and the code skeleton on the side shows the three nested loops feeding it. As n grows the cube's volume — the work — swells far faster than the square's area.

Step 8 — O(2ⁿ): the doubling tree (a binary choice per item)

WHAT. For each of the n items, make one binary choice — take it or skip it. Count all the ways.

WHY EXPONENTIAL. Each new item doubles the number of possibilities, because it plugs into every existing combination twice (once "taken", once "skipped"):

item 1 2 \times item 2 2 \times \dots \times item n 2 = 2^{n}

As a recurrence, "solve for n items = twice solve for n−1 items":

T (n) = two branches 2 T (n - 1) + c ⟶ O (2^{n})

Note the crucial difference from Step 3: here n sits in the exponent (it pushes 2 upward), whereas in $lo g n$ the n was inside the log. Exponent-in-the-power = explosion; that's why naive recursive Fibonacci and brute-force subset search are hopeless past ~40 items (deep dive: Dynamic-Programming tames these).

PICTURE. Figure s08 grows a binary tree: 1 node → 2 → 4 → 8, doubling each level, with the leaf count $2^{n}$ braced at the bottom. Then it overlays $2^{n}$ against $n^{2}$ on the arena and marks the crossing near n≈4 where exponential overtakes quadratic forever.

Step 9 — O(n!): every ordering (the fastest explosion)

WHAT. Enumerate every possible order (permutation) of n items — brute-force Travelling Salesman, generating all arrangements.

WHY FACTORIAL, and why it beats 2ⁿ. Building an ordering: n choices for the first slot, then n−1 for the second, and so on:

n! = 1st slot n \times 2nd (n - 1) \times \dots \times last 2 \times 1

Now stack it against $2^{n}$ factor by factor — both are products of n numbers:

n! = 1 \cdot 2 \cdot 3 \cdot 4 \dots n, 2^{n} = 2 \cdot 2 \cdot 2 \cdot 2 \dots 2

From the third factor onward ( $3, 4, 5, \dots$ ) every factor of $n!$ is larger than the matching 2. So $n!$ pulls ahead — first at n=4 ( $24 > 16$ ) — and the gap widens without bound. Factorial is its own, worse class; this is why exact TSP is intractable for large n.

PICTURE. Figure s09 places $n!$ against $2^{n}$ term-by-term as two rows of factors, highlighting where $n!$ 's factors overtake the constant 2s, then plots both curves so $n!$ visibly tears away above $2^{n}$ .

The one-picture summary

WHAT. Every class from Step 2 to Step 9, on one arena, with the two crossings marked and the ladder read off by who ends up on top.

PICTURE. Figure s10 layers all eight curves — flat $O (1)$ , the crawling $lo g n$ , the straight ramp $n$ , the slightly-bent $n lo g n$ , the parabola $n^{2}$ , the steeper cube $n^{3}$ , the wall-climbing $2^{n}$ , and the near-vertical $n!$ . The vertical stacking on the right edge is the ladder $O (1) < lo g n < n < n lo g n < n^{2} < n^{3} < 2^{n} < n!$ .

Recall Feynman: the whole walkthrough in plain words

Picture a big arena. The floor counts how many sheets of homework you're given; the wall counts how much work you do.

Grab the top sheet only → flat line ( $O (1)$ ). Bigger pile, same effort.
Play higher/lower on a sorted pile, tearing it in half each guess → a line that barely rises ( $lo g n$ ): a million sheets, ~20 guesses.
Read every sheet once → a straight ramp ( $n$ ).
Split the pile in halves, sort each, merge — $lo g n$ levels of $n$ -work each, added up → a slightly steeper ramp ( $n lo g n$ ).
Compare every sheet to every other → a parabola ( $n^{2}$ ), the filled square of all pairs.
Do that comparison nested three deep → a solid cube of work ( $n^{3}$ ).
For each sheet decide keep-or-toss and try every combination → a doubling tree that shoots up the wall ( $2^{n}$ ); it passes the parabola around 4 sheets.
Try every possible order to stack them → a curve that goes almost straight up ( $n!$ ), leaving even $2^{n}$ far below from 4 sheets on. The faster your curve climbs the wall as sheets pile on the floor, the worse — and now you've seen exactly why the ladder is ordered the way it is.

Related: the parent topic · 3.1.03-Best-Worst-Average-Case · 3.1.01-Big-O-Notation