Asymptotic Notation as Sets of Functions, Not Growth Rates

A statement such as “this routine is O(n²)” is a membership claim: the running-time function belongs to a set of functions identified by how fast they can grow. Treating the symbol as a growth rate rather than a set causes most of the reasoning errors that follow, because sets are not symmetric, not total, and not closed under the operations people expect.

The definition quantifies over two witnesses

For functions from non-negative integers to non-negative reals, the class is defined by a pair of witnesses:

O(g)  = { f : there exist c > 0 and n₀ ≥ 0 with f(n) ≤ c·g(n) for all n ≥ n₀ }
Ω(g)  = { f : there exist c > 0 and n₀ ≥ 0 with f(n) ≥ c·g(n) for all n ≥ n₀ }
Θ(g)  = O(g) ∩ Ω(g)
o(g)  = { f : for every c > 0 there exists n₀ ≥ 0 with f(n) < c·g(n) for all n ≥ n₀ }

The membership test for O is existential: any single pair of witnesses suffices. For 3n + 7 the choice c = 4, n₀ = 7 works, since 3n + 7 ≤ 4n exactly when n ≥ 7. The same function also belongs to O(n²), because 3n + 7 ≤ 10n² for every n ≥ 1. Nothing about the definition selects the tightest class, which is why a bound is only as informative as the smallest class known to contain the function.

The little-o definition differs in the quantifier order. There c is not a witness the writer chooses; the claim must hold for every positive c, so n is eventually below every multiple of n log n, which gives n ∈ o(n log n) while n log n ∉ O(n). That difference is the entire content of the distinction between a bound that is asymptotically strict and one that is merely an overestimate.

Equality in the notation is one-directional and misleading. Writing 2n² + 3n = O(n²) asserts membership of the left side in the set on the right; it does not license rewriting O(n²) as 2n² + 3n elsewhere in an expression. Substituting sets into algebra produces nonsense such as O(n) − O(n) = O(1), which claims a bound on a difference of two independent functions.

Asymptotic class and case analysis are independent axes. A function may take Θ(n) steps on some inputs and Θ(n²) steps on others; the class constrains only the bound being asserted, and a claim about worst-case behaviour is a claim about the maximum over inputs of that size. The three-way pairing of best, average, and worst case with an arbitrary class is what makes the phrase “average case O(n log n)” mean expected cost rather than a bound, a distinction that the probabilistic machinery in expected and amortized cost makes precise.

What a constant factor can and cannot absorb

Logarithm bases are absorbed. Since log_b n = log_2 n / log_2 b, the two functions differ by the constant 1 / log_2 b, and log_2 10 ≈ 3.32. The unqualified class O(log n) is therefore well defined, even though the numeric values differ substantially: at n = 10⁶, log₂ n ≈ 19.9 while log₁₀ n ≈ 6. The class is the same; the counts are not.

Nested logarithms are not absorbed. At n = 2¹⁰²⁴, the binary logarithm is 1024 and the second iterate is 10, a factor of about 100 apart. A structure that answers a query in log log n probes is not merely a constant-factor improvement over one that takes log n probes at that size, and algorithms that reach the iterated-logarithm regime usually do so through a different mechanism entirely, as inverse-Ackermann and iterated-logarithm bounds describe.

A constant factor inside an exponent survives. The function 2^(n/2) is in O(2^n), since the ratio 2^(n/2) / 2^n = 2^(−n/2) tends to zero, so 2^(n/2) ∈ o(2^n). The two are not in the same Θ class, and the gap widens with n. Constants in the base of an exponential are absorbed only into a changed exponent: 3^n = 2^(n log₂ 3), and log₂ 3 ≈ 1.585. This is the reason exact exponential algorithms are classified by the constant multiplying n in the exponent rather than by the base, and why a bound of O(2^{cn}) with c < 1 is a substantive improvement over O(2^n).

Two inputs, one bound

Graph algorithms are naturally bounded by two parameters, the vertex count n and the edge count m. Breadth-first search over adjacency lists touches each vertex once and each edge twice, giving Θ(n + m); the same search over an adjacency matrix scans a full row per vertex, giving Θ(n²) regardless of density. Because m ≤ n², the first bound implies the second in the trivial sense that n + m ≤ 2n² for n ≥ 1, and for a sparse graph the two differ by a factor of n.

For positive n and m, the sum and the maximum are interchangeable: max(n, m) ≤ n + m ≤ 2·max(n, m). At n = 5, m = 9 the sum is 14 and the maximum 9, a ratio of 1.56, and the ratio reaches 2 only when n = m. So n + m ∈ Θ(max(n, m)), and either form names the same set of functions.

Products do not collapse this way. At n = m = 1000, n + m is 2000 while n·m is 10⁶. Bipartite matching with the Hopcroft–Karp algorithm runs in O(m√n), and the Edmonds–Karp maximum-flow algorithm runs in O(nm²). Neither reduces to a single-parameter form, and for a graph with m = Θ(n) the matching bound is smaller than the flow bound by a factor of n^{3/2}.

def merge_scan(n, m):
    """A sequential merge of two sorted runs costs n + m element visits."""
    return n + m

for n, m in ((5, 9), (100, 100), (1 << 20, 3)):
    s = merge_scan(n, m)
    print(n, m, s, max(n, m), round(s / max(n, m), 3))

The printed ratio stays inside [1, 2] for every pair, which is the inequality above restated as a measurement of the bound rather than of any machine.

Where the notation quietly swaps the machine

Every asymptotic claim is relative to a cost model, and the choice of model can change the class. Under a word-RAM model in which one arithmetic operation on a machine word is one step, adding two 64-bit integers is constant time. Multiplying two k-bit integers is not: schoolbook multiplication performs Θ(k²) bit operations and Karatsuba’s method is roughly Θ(k^1.585). A statement that an algorithm runs in O(n) time is therefore a statement about a model in which the size of the operands is bounded, and the assumption is invisible until the numbers in question exceed a word. The word-RAM cost model is where that boundary is drawn.

Sorting shows the same sensitivity. Comparison sorting costs Θ(n log n) comparisons by the decision-tree argument sketched in comparison lower bounds from decision trees, while radix sorting n keys of b bits in r-bit digits performs Θ((b/r)(n + 2^r)) operations. Neither dominates the other across all parameter ranges, and the comparison is meaningful only after fixing the model and the digit width.

Space bounds follow the same convention. An algorithm using O(1) auxiliary space uses a number of machine words bounded by a constant independent of the input size, which is a different and stronger statement than “uses a small amount of memory”. An in-place array reversal that swaps pairs uses O(1) auxiliary words; a recursive version that descends to depth n uses Θ(n) words of stack even though it allocates nothing explicitly.

What the threshold hides

The witness n₀ is what allows the definition to ignore everything small, and real implementations live in that discarded region. A cache line holds 64 bytes on the common architectures, so a linear scan of a contiguous array performs roughly one memory fetch per 16 four-byte elements, while a linked-list traversal performs one dependent fetch per element. Both are Θ(n), and their constant factors can differ by an order of magnitude.

Library sort implementations exploit exactly this. The asymptotically superior merge or quicksort variants are typically abandoned for insertion sort once a run falls below a few tens of elements, because the comparison count is not the dominant term at that size and the constant factor is. Merging a dynamic array’s two halves is Θ(n) in copies, and the amortized argument for growing that array is about sequences rather than individual operations, as analysed in dynamic arrays and amortized accounting.

The practical summary is that a class describes the limiting shape of a function under a fixed cost model, up to a multiplicative constant applied to the function’s value and above a threshold that may be large. Constants in exponents, extra input parameters, and changes to the model are outside the notation’s tolerance, and a bound that ignores them is not wrong but incomplete.