Big-O Precisely: What O, Ω and Θ Each Claim, and When the Faster Algorithm Loses

The three symbols, stated properly

All three compare growth rates as \(n \to \infty\), discarding constants. For non-negative \(f\) and \(g\):

Read them as claims. \(O\) says “grows no faster than”; \(\Omega\) says “grows no slower than”; \(\Theta\) says “grows at the same rate as”. Three consequences people trip over:

• \(O\) is an upper bound, so a linear algorithm is \(O(n^2)\) — the statement is true and useless. When you say an algorithm “is \(O(n^2)\)” you are conventionally asserting the tight bound, which is really a \(\Theta\) claim. Say \(\Theta\) when you mean it.
• The bound is on the function, not the algorithm. “Quicksort is \(O(n \log n)\)” is meaningless until you say which function: its expected running time, or its worst case? Those differ.
• \(\Omega\) belongs to problems more than to code. “Comparison sorting is \(\Omega(n\log n)\)” says no comparison algorithm can do better — a statement about every possible algorithm, proved in the sorting post.

Worst, average, amortised

These are three different quantifiers over the input, and confusing them is the most common way to be wrong while sounding right.

Worst case maximises over inputs of size \(n\). It is a guarantee: nothing can be slower. Average case takes an expectation over an assumed distribution of inputs, and that assumption is part of the claim — quicksort’s \(\Theta(n\log n)\) average assumes a uniformly random permutation, which your already-sorted log file is not.

Amortised is different in kind. It is still worst case, but over a sequence: if any sequence of \(m\) operations costs \(O(m \cdot T)\) in total, each operation is amortised \(O(T)\), even though individual ones may be much dearer. No randomness is involved, so an adversary cannot break it. Appending to a dynamic array is amortised \(O(1)\) with worst-case \(O(n)\) on the resize step; the arrays post derives it from a geometric series.

Reading a cost off loops

Sequential blocks add and take the max; nested loops multiply — but only when the inner bound does not depend on the outer index.

def count_close_pairs(xs, eps):
    n = len(xs)
    total = 0
    for i in range(n):              # n iterations
        for j in range(i + 1, n):   # n - 1 - i iterations
            if abs(xs[i] - xs[j]) < eps:
                total += 1
    return total

The inner loop runs \(n-1-i\) times, so the total is \(\sum_{i=0}^{n-1}(n-1-i) = n(n-1)/2\), which is \(\Theta(n^2)\): the triangular shape halves the constant but not the growth. A loop that doubles its counter, while i < n: i *= 2, runs \(\lfloor \log_2 n\rfloor + 1\) times, which is where every \(\log\) in this book comes from — repeated halving or doubling.

The trap is a hidden loop: if x in some_list is \(\Theta(n)\), so wrapping it in a loop is \(\Theta(n^2)\), and s += chunk in a loop copies the whole string each time. Both look like one line.

Reading a cost off recursion

For a recursion that splits into \(a\) subproblems of size \(n/b\) plus \(f(n)\) work to divide and combine,

the Master theorem compares \(f(n)\) with \(n^{\log_b a}\), the total cost of the leaves:

1. If \(f(n) = O(n^{\log_b a - \varepsilon})\) for some \(\varepsilon > 0\), the leaves dominate: \(T(n) = \Theta(n^{\log_b a})\).
2. If \(f(n) = \Theta(n^{\log_b a}\log^k n)\) with \(k \ge 0\), every level costs the same: \(T(n) = \Theta(n^{\log_b a}\log^{k+1} n)\).
3. If \(f(n) = \Omega(n^{\log_b a + \varepsilon})\) and \(a f(n/b) \le c f(n)\) for some \(c<1\) and large \(n\), the root dominates: \(T(n) = \Theta(f(n))\).

Strassen is the interesting row: it does seven multiplications where the blocked algorithm does eight, and that single saved subproblem is what drops the exponent from \(3\) to \(2.807\).

Space complexity

Count everything that lives simultaneously, including the call stack. Merge sort needs \(\Theta(n)\) auxiliary space for the merge buffer; quicksort partitions in place but its recursion depth is \(\Theta(\log n)\) expected and \(\Theta(n)\) worst case, which is why real implementations recurse on the smaller side. A recursive tree traversal costs \(\Theta(h)\) stack space for tree height \(h\) — fine at \(h = 20\), a crash at \(h = 10^6\), as the recursion post shows.

Why the better algorithm sometimes loses

Two forces. First, constants: a \(\Theta(n\log n)\) algorithm with a large constant loses to a \(\Theta(n^2)\) one until \(n\) is large enough, and “large enough” is sometimes past any \(n\) you will see.

Second, memory. The model behind big-O charges \(1\) per memory access, and real hardware does not. A cache line is fetched as a block — 64 bytes on x86-64 — so a sequential scan of an array amortises one fetch over many elements, while pointer-chasing through a linked list pays a fresh miss per node. Two algorithms with identical asymptotics can differ substantially on this alone, which is why array-backed structures dominate in practice.

References

1. Knuth, D. E. Big Omicron and big Omega and big Theta. ACM SIGACT News 8(2), 18–24, 1976.
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, 4th ed. MIT Press, 2022 — ch. 3–4 for asymptotics, the Master theorem and amortised analysis.
3. Bentley, J. L., Haken, D., & Saxe, J. B. A general method for solving divide-and-conquer recurrences. ACM SIGACT News 12(3), 36–44, 1980.
4. Strassen, V. Gaussian elimination is not optimal. Numerische Mathematik 13, 354–356, 1969.
5. Peters, T. listsort.txt — CPython’s description of Timsort, including the binary-insertion cutover for short runs.
6. Drepper, U. What Every Programmer Should Know About Memory. 2007.