Big O Notation

Big O describes how an algorithm's cost grows as the input grows. It is deliberately not a measurement in seconds — those change with the machine, the JIT and the weather. The growth rate does not.

Why not just time it?

Because "0.3 seconds" answers a question nobody asked. The useful question is what happens at ten times the data.

Read the last two rows. At n = 10 the difference between O(n²) and O(2ⁿ) is a rounding error — both finish instantly. At n = 100 one takes ten thousand steps and the other will not finish before the sun goes out. That is what Big O is for: it tells you which algorithms have a future.

The classes, with an example each

O(1) — constant. Cost does not depend on n. Array indexing, a hash lookup, pushing onto a stack.

O(log n) — logarithmic. Each step discards a fraction of the input, usually half. Binary search, or descending a balanced tree. This is nearly as good as constant: doubling the data adds one step.

O(n) — linear. Every element is touched once. Summing an array, searching an unsorted list.

O(n log n) — linearithmic. The best a comparison sort can do. Merge sort, heap sort, and Java's Arrays.sort.

O(n²) — quadratic. A loop inside a loop over the same input. Bubble sort, or comparing every pair. Fine at n = 100, painful at n = 10,000, hopeless at n = 1,000,000.

O(2ⁿ) — exponential. Each element doubles the work. The naive recursive Fibonacci, or generating every subset. Usable only for tiny n, and generally a sign that dynamic programming applies.

Reading it off the code

Count how many times the innermost work runs as a function of n.

// O(1) - one operation regardless of size
int first = values[0];

// O(n) - the loop runs n times
for (int value : values) {
    total += value;
}

// O(n^2) - n iterations, each doing n more
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        doSomething(i, j);
    }
}

// O(log n) - the counter DOUBLES, so it reaches n in log2(n) steps.
// This is the shape to recognise: multiply or divide, not add or subtract.
for (int i = 1; i < n; i *= 2) {
    doSomething(i);
}

// O(n log n) - an O(n) loop wrapped around an O(log n) one
for (int i = 0; i < n; i++) {
    for (int j = 1; j < n; j *= 2) {
        doSomething(i, j);
    }
}

Two traps in that list. Nested loops are only O(n²) when both run over n — a loop over a fixed 16 elements inside a loop over n is O(n), not O(16n) and certainly not O(n²). And a loop whose counter multiplies is logarithmic no matter how much it looks like the linear one.

Why constants get dropped

O(2n + 50) is written O(n). Not because the 2 and the 50 do not exist, but because they stop mattering as n grows — at n = 1,000,000 the 50 is invisible, and the 2 does not change the shape of the curve.

Rules that follow:

• Drop constant factors. O(3n) → O(n).
• Keep only the dominant term. O(n² + n + 100) → O(n²).
• Sequential blocks add — and then the smaller is dropped. Two separate loops over n are O(n) + O(n) = O(n).
• Nested blocks multiply. O(n) inside O(n) is O(n²).

⚠️ But do not read "constants do not matter" as advice about your code. They matter enormously in practice — an algorithm with a factor of 100 is a hundred times slower at every n. Big O says the constant does not change the growth, not that it does not change the runtime.

Best, average and worst case

These are different questions from Big O, and conflating the two is the most common confusion in the whole topic.

Take searching an unsorted array for a value:

• Best case — it is the first element. One comparison.
• Average case — about n/2 comparisons.
• Worst case — it is last, or absent. n comparisons.

Unless someone says otherwise, quote the worst case, because that is what you have to survive. There is one important exception worth naming: quick sort is O(n²) in the worst case and is still the default sort in most standard libraries, because that worst case is vanishingly rare with a decent pivot and its average O(n log n) has a very small constant.

Amortised complexity

A third thing again: the average cost per operation across a sequence.

ArrayList.add is usually O(1), but occasionally the array is full and it copies everything — O(n). Because the capacity doubles, those copies get rarer at exactly the rate they get more expensive, and n adds cost O(n) in total. So add is amortised O(1): not "usually fast and sometimes slow", but provably O(1) on average over any sequence. The ArrayList post works through the arithmetic.

Space complexity

Same notation, applied to memory, and counting the extra space beyond the input.

• O(1) — a fixed number of variables. Quick sort's partitioning, iterative binary search.
• O(log n) — the recursion stack of a well-implemented quick sort.
• O(n) — merge sort's buffer, or a memoisation table.

This is exactly the merge sort versus quick sort trade: identical O(n log n) time, but merge sort needs O(n) space and quick sort does not. It is also why the O(n) memo that turns Fibonacci from O(2ⁿ) into O(n) is such an obvious win — an array against an eternity.

What to remember

• Big O is about growth, not seconds.
• Multiply-or-divide loops are logarithmic; add-or-subtract loops are linear.
• Drop constants and lower-order terms; keep the dominant one.
• Quote the worst case by default, and know where the average case is the honest answer.
• Amortised is not the same as average, and both differ from best/worst case.
• Track space as well as time — sometimes it is the deciding one.

Next: Omega and Theta — what Big O leaves out.