Big-O: how we judge algorithms

A textbook algorithm is unambiguous, finite (it always stops) and correct for every valid input. We study two costs: time (how many basic operations it performs) and space (how much extra memory it uses). Both are measured as functions of the input size, usually written n: the number of items in a list, the number of characters in a text, and so on.

Analysis usually assumes a simple abstract machine where each basic operation (compare, add, read or write one memory cell) takes one unit of time. Real machines differ, but the way the count grows with n carries over, which is why the results are so durable. The abstraction ignores effects such as caching, so measured timings still matter in practice (see the last section).

We write f(n) is O(g(n)) when, for large enough n, f(n) never exceeds some constant multiple of g(n). So O(3n + 7) is simply O(n): constants and lower-order terms are dropped because they stop mattering as n grows. Strictly, Big-O is an upper bound. When a bound is tight in both directions the notation is Theta; people often say "Big-O" informally when they mean the tight bound, and this series does the same.

Logarithms here are base 2, but the base only changes a constant, so O(log n) needs no base. Exponential cost, as in checking every subset of n items, doubles with every extra item, so it is practical only for very small n. Some problems have no known fast method, and a large area of computer science studies where the line falls between "fast enough" and "hopeless". Polynomial classes such as n squared and n cubed sit between the comfortable ones and the exponential ones.

The worst case is a guarantee: it will never be slower. The average case needs an assumption about how inputs are distributed, so state it. The best case is rarely useful alone. They can differ sharply: quick sort is O(n log n) on average but O(n squared) in the worst case, while merge sort is O(n log n) in all three. Naming which case a bound refers to is part of stating it precisely.

Space complexity counts the extra memory beyond the input: merge sort needs O(n), while insertion sort needs O(1). Recursion also uses memory for its call stack.

Amortised cost is the average cost per operation over a whole sequence, even when single operations vary. A growable array that doubles its capacity when full occasionally copies everything (expensive), but over many appends the total copying is proportional to the number of appends, so each append is amortised O(1). It is a guarantee over a sequence, not a probability.

An algorithm taking 100n steps is O(n) and can lose to one taking n squared steps when n is below 100. Real machines also reward memory access patterns that stay close together, so two methods with equal step counts can run at different speeds. This is why practical sorting and searching code often combines methods and why profiling beats guessing. Big-O tells you what happens as n grows; measurement tells you what happens at the n you actually have.