Big-O Notation — The Language of Algorithmic Complexity

Why it matters

Constant factors change every hardware generation. Exponents do not. A compiler upgrade, a faster core, or a rewrite from Python to C buys a one-time multiplier somewhere between 2x and 100x; moving from quadratic to linearithmic buys a multiplier that grows without bound as the data grows. That asymmetry is the whole reason a notation that deliberately discards constants is worth using at all: it isolates the part of a performance story that survives every change to the machine underneath it.

The same discarding is what makes asymptotic analysis useless for the question people most often ask of it. It cannot tell you whether a request will finish in 3 ms or 300 ms. It tells you what happens to that number when the input doubles. Treating a complexity class as a performance prediction rather than a scaling prediction is the single most common way practitioners get burned by it -- usually in the form of picking the theoretically superior structure and shipping something measurably slower.

Used correctly it answers exactly two questions: will this survive the input sizes we expect, and which of these candidate approaches deserves to be benchmarked. Everything below is about answering those two precisely, and about knowing when the answer stops being trustworthy.

What O, Omega and Theta actually say

All three are sets of functions, defined by the same shape of statement: there exist constants such that, past some point, one function is sandwiched by another.

O(g)     = { f : there exist c > 0, n0 > 0 with 0 <= f(n) <= c*g(n)   for all n >= n0 }

Omega(g) = { f : there exist c > 0, n0 > 0 with 0 <= c*g(n) <= f(n)   for all n >= n0 }

Theta(g) = O(g) intersect Omega(g)
         = { f : there exist c1, c2 > 0, n0 > 0 with
                 c1*g(n) <= f(n) <= c2*g(n)   for all n >= n0 }

Three quantifiers carry all the meaning. The constant c absorbs every constant factor, which is what makes the notation machine-independent. The threshold n0 absorbs every small-input anomaly, which is what makes it a statement about growth. And "for all n >= n0" is what makes it a claim about the tail of the function rather than about any particular input.

The strict forms are worth knowing because they are the ones that express "strictly smaller order". f is o(g) when the inequality holds for every positive c, not merely for some -- equivalently f(n)/g(n) tends to zero. So n log n is o(n^2) but not o(n log n), while n^2 is O(n^2) but never o(n^2).

The same three quantifiers explain, mechanically, why lower-order terms drop -- this is a consequence, not a convention. Take f(n) = 3n^2 + 5n + 7. For every n >= 7 the tail 5n + 7 is at most n^2, so f(n) <= 4n^2 there; witness c = 4 and n0 = 7, and f is O(n^2). The matching lower bound is free at c = 3, so f is Theta(n^2). Nothing was rounded off: the single constant c has room to swallow every term growing slower than the leading one, and n0 is exactly the machinery that lets it, because below n0 the smaller terms genuinely can dominate and the bound makes no claim there.

One notational trap: f(n) = O(g(n)) is set membership written with an equals sign, and it is one-directional. Reading the "=" as "is" keeps you honest. O(n) = O(n^2) is a true statement left to right and a false one right to left, which is why chains of such equalities have to be read in a single direction.

Why an O(n log n) sort is also O(n^2)

Merge sort's running time is Theta(n log n). Since n log n is at most n^2 for every n >= 1, merge sort is also O(n^2). And O(n^3). And O(2^n). Every one of those statements is correct. O is a ceiling, and nothing in the definition requires the ceiling to be a low one.

This is not a pedantic curiosity, because published bounds exploit the looseness deliberately. When the tight bound is unknown, O is the only honest thing to write. Matrix multiplication is the standard example: the best known upper bound sits around O(n^2.37) and the only unconditional lower bound is the trivial Omega(n^2) for reading the input, so nobody can write Theta for it. Contrast union-find, where O(m alpha(n)) for m operations is matched by a proven lower bound in the cell-probe model, making it tight within that model.

The practical habit this should produce: when you read O in a paper or a README, ask whether it is loose by necessity or loose by convention. And when you state a bound on your own code, prefer Theta when you can defend it. Theta is the stronger claim -- it requires you to also argue that the algorithm cannot do better, which usually means exhibiting an input family that forces the cost.

The mirror-image error is treating Omega as "the best case". Omega is a lower bound on whatever function you have chosen to talk about. "Insertion sort's worst-case time is Omega(n^2)" is a meaningful, true, and useful statement -- it says the quadratic behaviour is unavoidable on bad inputs, not that it happens on good ones.

Worst case is not the same thing as big-O

This is the confusion worth spending real effort on, because it survives years of practice. There are two independent choices, and people fuse them into one.

Axis one: which input of size n. A fixed algorithm does not have a single running time at size n; it has one per input. Collapsing that set to a number means choosing the maximum (worst case), the minimum (best case), or an average under some distribution. Each choice produces a different function of n.

Axis two: how you bound the function you chose. Having picked a function, you can put an upper bound (O), a lower bound (Omega), or a tight bound (Theta) on it.

Any bound applies to any case. All of these are correct and none is "the" complexity of insertion sort: its best-case time is Theta(n), its worst-case time is Theta(n^2), its worst-case time is also O(n^3), and its average-case time over uniform random permutations is Theta(n^2). Quicksort's worst case is Theta(n^2) while its average is Theta(n log n) -- two different functions, each with its own tight bound.

The reason the axes get welded together is sociological: the literature usually quotes the worst case and usually writes O, so the two symbols co-occur until they look synonymous. They are not, and the giveaway that someone has fused them is a sentence like "quicksort is O(n^2)" delivered as a criticism. It is true; it is also true of every sorting algorithm ever written.

The average-case option hides an assumption the other two do not. An average requires a probability distribution over inputs, and the distribution nearly always assumed -- uniform random permutation -- is a fiction. Production data arrives sorted, reverse-sorted, nearly sorted, heavily duplicated, or chosen by someone who read your source. Quicksort's average-case guarantee evaporates the moment the input is a sorted array and the pivot is the first element, which is a real and repeatedly rediscovered production incident rather than a textbook hypothetical.

Reading a bound off a loop

Three loop shapes cover most hand analysis, and the sums are worth memorising rather than rederiving.

# 1. Triangular:  1 + 2 + ... + (n-1) = n(n-1)/2   ->  Theta(n^2)
for i in range(n):
    for j in range(i):
        work()

# 2. Doubling:  the counter takes log2(n) values    ->  Theta(log n)
i = 1
while i < n:
    i *= 2

# 3. Harmonic:  n/1 + n/2 + ... + n/n = n*H(n)      ->  Theta(n log n)
for step in range(1, n + 1):
    for k in range(step, n + 1, step):
        work()

The composition rules are short. Sequential blocks add, so the largest term wins outright. Nested loops multiply only when their bounds are independent of each other -- the triangular case above is the reminder that when the inner bound depends on the outer counter you have to sum, not multiply, and the result happens to be the same class here but is not in general. A counter that is multiplied rather than incremented gives a logarithmic number of iterations, and the multiplier only changes the logarithm's base, which is a constant factor.

The harmonic pattern is the one people misjudge. Restrict its outer loop to primes and the same nested shape collapses to Theta(n log log n) -- the sieve of Eratosthenes. Same structure, different index set, different class; there is no shortcut around actually summing the inner work.

The commoner failure is not a mis-summed loop but an operation that looks constant and is not. list.pop(0) shifts every remaining element. s = s + t inside a loop copies the whole accumulated string each time, making n concatenations Theta(n^2). Slicing a string or list copies it. Membership testing with in is a linear scan on a list and a hash lookup on a set. Most accidental quadratics in real code are a single innocent-looking loop with one of these hidden inside it, which is why reading a bound off the source requires knowing the cost model of your standard library, not just the loop nesting.

Recurrences and the Master Theorem

Divide-and-conquer costs are recurrences, and one theorem solves the common shape. It has preconditions, and the preconditions are where it is usually misapplied.

Applies to:  T(n) = a*T(n/b) + f(n)
             with a >= 1 and b > 1 constants, f(n) positive for large n.
             Floors and ceilings on n/b do not change the answer.

Watershed:   n^(log_b a)     -- the total work sitting in the leaves.

Case 1   f(n) = O( n^(log_b a - eps) )          for some eps > 0
         =>  T(n) = Theta( n^(log_b a) )              leaves dominate

Case 2   f(n) = Theta( n^(log_b a) * (log n)^k )      for some k >= 0
         =>  T(n) = Theta( n^(log_b a) * (log n)^(k+1) )   levels tie

Case 3   f(n) = Omega( n^(log_b a + eps) )      for some eps > 0
         AND  a*f(n/b) <= c*f(n) for some c < 1 and all large n
         =>  T(n) = Theta( f(n) )                     the root dominates

Two details get dropped and both matter. The eps in cases 1 and 3 demands a polynomial separation between f and the watershed, not merely that one is smaller. And the regularity condition in case 3 is not decorative: it is what guarantees the per-level costs form a decreasing geometric series, and without it a pathological f can oscillate so that no level ever dominates.

The gap those details create is real. Take T(n) = 2T(n/2) + n/log n. Here log_b a = 1, and n/log n is smaller than n but not polynomially smaller, so no case applies; a recursion tree gives Theta(n log log n). Unequal splits are outside the theorem entirely -- the median-of-medians recurrence T(n) = T(n/5) + T(7n/10) + n needs Akra-Bazzi or a direct substitution argument. And T(n) = T(n-1) + n is not of this form at all; the subproblem shrinks by subtraction, not division, so unroll it by hand to n(n+1)/2 = Theta(n^2).

Strassen and the naive algorithm differ only in a -- seven recursive multiplications instead of eight -- and that single unit of a is the entire difference between n^2.807 and n^3. Reading the table this way is the point of the theorem: it tells you which knob in a divide-and-conquer design actually moves the exponent.

Amortized analysis and the doubling argument

A dynamic array append is Theta(n) when it resizes and Theta(1) when it does not, yet n appends starting from empty cost Theta(n) in total. Amortized analysis is the machinery for stating that cleanly, and the doubling array is the cleanest place to see what kind of claim it makes.

The aggregate view is arithmetic. Across n appends the resizes copy 1 + 2 + 4 + ... + 2^k elements, a geometric series summing to less than 2^(k+1) <= 2n, on top of n unit writes. Total under 3n, so 3 per append. The growth factor is doing all the work here: growing by a constant +c instead makes the copy costs an arithmetic series totalling Theta(n^2/c), which is Theta(n) per append and the reason no serious vector implementation grows by a fixed increment. Any factor above 1 gives the geometric collapse; the choice between 2 and 1.5 is about allocator block reuse, not about complexity.

The potential method makes the same argument mechanical, and generalises to structures where the aggregate sum is hard to write down. Define a potential Phi mapping each state to a number, and charge each operation its amortized cost = actual cost + Phi(after) - Phi(before). For the doubling array take Phi = 2*num - size, where num is the element count and size the capacity.

Phi = 2*num - size

Validity (both required, and both are easy to lose):
  Phi(empty) = 0   -- start from size = 0, not from a preallocated capacity
  Phi >= 0 always  -- doubling with no shrinking keeps num >= size/2

Append with room:   actual 1,  Phi rises by 2
                    amortized = 1 + 2                       = 3

Append that resizes at element i   (i >= 2; the very first append just
                                    expands capacity 0 to capacity 1):
   actual = i          (one write + i-1 copies)
   before: num = i-1, size = i-1        -> Phi = 2(i-1) - (i-1) = i-1
   after:  num = i,   size = 2(i-1)     -> Phi = 2i - 2i + 2    = 2
                    amortized = i + 2 - (i-1)                = 3

Both branches amortize to exactly 3, so append is O(1) amortized. Note the two validity conditions explicitly: if the array starts with a nonzero capacity and zero elements then Phi is negative and the whole argument is invalid, because the amortized costs are only guaranteed to upper-bound the real ones when Phi never drops below its starting value.

What the word "amortized" means is worth stating flatly, because it is routinely misread as a synonym for "average". It is a worst-case bound on a sequence. There is no probability distribution anywhere in the argument, no assumption about inputs, and no chance of being unlucky. Any n appends cost at most 3n, full stop.

It also carries three caveats that bite in production. It says nothing about an individual operation -- the append that resizes a 100-million-element vector really does copy 100 million elements, so if you own a p99 latency target, the amortized bound is not the number you report, and real-time systems use deamortized structures that spread the copy across subsequent operations. It does not survive persistence: the stored credit can be spent once, so if a caller can snapshot the structure just before an expensive operation and re-trigger it repeatedly, the amortized bound degrades to the worst case per call. And shrinking needs hysteresis -- halving the capacity the moment num falls to size/2 lets an append/pop pair at the boundary force a full copy on every single operation, which is why implementations shrink at size/4 instead.

Expected time, and why randomization is a stronger guarantee

Randomized quicksort chooses its pivot uniformly at random. Its expected running time is Theta(n log n), and the expectation is taken over the algorithm's own coin flips, not over a distribution of inputs. That distinction is the entire value proposition: the guarantee holds for every input, including sorted, reverse-sorted, and inputs constructed by someone who has read your code.

Compare that with deterministic quicksort's average case, which is the same Theta(n log n) but conditional on your data actually being a uniform random permutation. One guarantee is a property of the algorithm; the other is a hope about the world. The quadratic worst case still exists in the randomized version -- it now requires the coins to conspire, which happens with probability that decays exponentially, rather than being reachable by a user who submits an already-sorted file.

Hash tables are where this bites hardest in practice. Expected O(1) lookup rests on keys distributing across buckets, and a fixed, publicly known hash function lets an attacker choose thousands of keys that collide into one bucket, turning every insert into a linear scan and a single HTTP request into a CPU denial of service. The fix is not a better asymptotic bound; it is randomization -- a per-process seed feeding a keyed hash such as SipHash -- which restores the expectation against an adversary who cannot see the seed.

Two categories are worth naming. A Las Vegas algorithm is always correct and has random running time, so you quote an expectation (randomized quicksort). A Monte Carlo algorithm has bounded running time and a bounded probability of a wrong answer, so its cost has two numbers -- time and error probability -- and you drive the second down by repeating the test, as Miller-Rabin does.

Space complexity, including the stack nobody counts

Space is analysed with the same notation and usually with less care. The first thing to pin down is which space you are counting: total space includes the input, auxiliary space excludes it, and any claim of "in-place, O(1) space" always means auxiliary and always excludes the output too. Merge sort needs Theta(n) auxiliary space for the merge buffer; heapsort needs Theta(1); that difference, not the comparison count, is often what decides between them.

The line item people forget is the recursion stack, which is auxiliary space whether or not you allocated it. In-place quicksort partitions with Theta(1) extra data but its stack depth is the recursion depth, which is Theta(n) in the worst case if you recurse into both partitions naively. Recursing into the smaller partition and looping on the larger one bounds the depth at log2 n, because the recursive call at least halves the remaining range each time. This is why every library quicksort does exactly that; it is a correctness fix for stack exhaustion, not an optimisation.

The limits are concrete. A default thread stack is around 8 MB on Linux and 1 MB on Windows, and at 64 to 100 bytes per frame a recursive depth-first search over a million-node path graph overruns it and dies with a segmentation fault rather than an exception. CPython caps recursion at 1000 frames by default and raises RecursionError instead, which is friendlier and equally fatal to the algorithm. The remedy -- an explicit stack on the heap -- changes no asymptotic bound at all and is purely about which memory region the frames live in.

Finally, the unit of space is a word, not a bit. Storing n indices into an n-element array is Theta(n) words but Theta(n log n) bits, because an index needs log n bits. The RAM model quietly assumes the word is wide enough, which the word-RAM model states honestly as w >= log n. It rarely matters until you are designing succinct structures, where the bit-level accounting is the entire point.

A concrete sense of scale

Complexity classes only become decision-making tools once they are attached to numbers. The table below assumes a machine retiring roughly 10^9 simple operations per second, which is the right order of magnitude for a single core running straightforward code.

The rightmost column is the one to internalise, because it is how the table is used in practice: given the class, how large an input can you afford? It is what makes an exponential exact algorithm perfectly reasonable at n = 20 -- Held-Karp solves a 20-city travelling salesman instance in seconds -- and what tells you at n = 200 that you need an approximation or a solver, not a faster CPU.

The left side carries the argument for caring about the class at all. At n = 10^6, quadratic is 17 minutes and linearithmic is 20 milliseconds: a factor of 50,000 that no amount of constant-factor tuning, vectorisation, or rewriting in a faster language will recover. Constant factors are worth chasing only once the class is right, and chasing them before that is the classic way to spend a week making an unusable program 3x less unusable.

When the abstraction lies

Three failure modes, all of which follow directly from what the definitions throw away.

Small n, where n0 has not been reached

The threshold n0 in the definition is real: below it the bound simply does not apply, and nothing in the theory says how far out n0 sits. This is why every production sort is a hybrid. Introsort falls back to insertion sort below roughly 16 elements; Timsort builds runs of 32 to 64 with binary insertion sort. Theta(n^2) with a tiny constant, no allocation and perfectly predicted branches beats Theta(n log n) with recursion and a merge buffer at those sizes, every time.

Constants that are astronomical

An algorithm can have the better exponent and never be worth running -- the standard term is "galactic". The fast matrix multiplication family that reached O(n^2.37) has constants placing its crossover point beyond any matrix that fits in a datacentre, while Strassen's O(n^2.807) crosses over in the low hundreds of rows and genuinely ships. AKS sorting networks achieve O(n log n) depth with a constant in the thousands. In each case the asymptotic statement is true and the engineering conclusion is the opposite of what it suggests.

Memory access patterns

Two Theta(n) traversals can differ by an order of magnitude: a contiguous array streams through the prefetcher, while a linked list serialises one full DRAM latency per node because the next address is not known until the current node arrives. Linear scan of a sorted integer array beats binary search up to roughly 64 to 128 elements, despite Theta(n) against Theta(log n), because the scan reads whole cache lines with perfect branch prediction and vectorised comparisons while the binary search jumps unpredictably. B-trees exist for exactly this reason: log_B n versus log_2 n is a constant factor of log_2 B, which is invisible asymptotically and is the difference between four block reads and forty.

The RAM model underneath all of this is a fiction

Every bound above is stated in the RAM model: unit-cost arithmetic, unit-cost access to any memory location, one processor executing one instruction at a time. All three assumptions are false on hardware built after about 1985, and knowing precisely how they fail is what lets you choose between two algorithms in the same class.

Memory is a hierarchy, not a flat array. L1 is around 1 ns, L2 around 4 ns, L3 around 15 to 20 ns, DRAM around 80 to 100 ns, and an NVMe read is 50 to 100 us. "One memory access" therefore spans five orders of magnitude, and an algorithm's real cost is dominated by which level it lands in rather than by how many accesses it issues. The external-memory model fixes this honestly by counting block transfers of size B instead of individual accesses, which is why a B-tree's O(log_B n) block reads is the meaningful bound for a database index and its O(log n) comparisons is not. Cache-oblivious algorithms reach the same bound without being told B.

Branches are not free either. A mispredicted branch costs roughly 15 to 20 cycles on a modern deep pipeline, which can exceed the work the branch was guarding. That is why branchless variants -- conditional moves in a binary search, arithmetic instead of a test in a partition step -- routinely win while executing strictly more instructions. And SIMD lanes and multiple cores contribute factors of 8 to 16 and 8 to 64 respectively, which are exactly the constant factors the notation discards.

Unit-cost arithmetic fails too, as soon as numbers stop fitting in a register. "O(log n) modular exponentiations" hides the fact that each multiplication of k-bit numbers is itself superlinear in k, which is why cryptographic cost is always quoted in bit operations.

The operational conclusion: when two candidates land in the same asymptotic class, asymptotic analysis has finished its job and has nothing further to contribute. Decide by measuring on representative data, with a standing bias toward whichever candidate touches memory sequentially and branches predictably, because those are the two constants that vary most.

Lower bounds: proving the problem, not the algorithm

An upper bound is exhibited by writing an algorithm. A lower bound is a proof about every algorithm that could ever be written within a model -- a far stronger and far rarer thing. The comparison-sorting bound is the canonical example and the argument is short enough to carry in your head.

Model any deterministic comparison-based sort as a decision tree. Each internal node is one comparison between two elements, with a child for each outcome; each leaf is the permutation the algorithm outputs on the inputs that reach it. For the algorithm to be correct, each of the n! possible input orderings must lead to its own leaf, since two different orderings need two different output permutations. So the tree has at least n! leaves. A binary tree of height h has at most 2^h leaves, giving 2^h >= n!, hence h >= log2(n!). Stirling's approximation gives log2(n!) >= n*log2(n) - n*log2(e), roughly n log2 n - 1.44n. The height is precisely the number of comparisons along the worst-case path, so every comparison sort performs Omega(n log n) comparisons on some input. Merge sort and heapsort meet that bound, so the comparison complexity of sorting is Theta(n log n) -- a closed question, which is unusual.

Read the model clause carefully, because it is where all the content is. This bounds algorithms that compare keys. Counting sort at O(n + k) and radix sort at O(d(n + k)) are not counterexamples; they never compare two keys, they use key values as indices, which requires assumptions about the key domain that comparison sorts do not make. Escaping the model is the standard way to beat a lower bound, and it always costs you generality. The same counting argument extends to randomized comparison sorts, bounding their expected comparisons by the same Omega(n log n).

What should stay with you is how rare this situation is. For most problems no useful lower bound is known: matrix multiplication's only unconditional bound remains the trivial Omega(n^2) needed to read the input, decades after the upper exponent started falling. That scarcity is why computational hardness is normally argued by reduction to a problem already believed hard, rather than proved outright -- a separate subject from the notation here, and one where the open questions are considerably older.