Asymptotic Notation & Bounds

## The formal definition Big-O is a statement about functions, not about code. We write `f(n) = O(g(n))` — read "f is Big-O of g" — when there exist a positive constant `c` and a threshold `n0` such that: ``` f(n) <= c * g(n) for all n >= n0 ``` In words: **beyond some input size, f is bounded above by a constant multiple of g.** Big-O names a *set* of functions (everything that grows no faster than g, up to a constant), and the claim "this algorithm is O(n)" says its running-time function belongs to that set. ## A worked example Suppose an algorithm performs exactly `3n^2 + 50n + 7` operations on an input of `n` records. Claim: this is O(n^2). Proof sketch: for `n >= 51`, we have `50n + 7 <= n^2`, so `3n^2 + 50n + 7 <= 4n^2`. Picking `c = 4` and `n0 = 51` satisfies the definition. Nobody memorizes these constants — the point is that *some* pair exists, which is all the definition asks. ## Why constants are dropped Two reasons, one practical and one formal: - **Step counting is ambiguous.** Is `a[i] + 1` one operation or three (index, load, add)? Different machines, compilers, and counting conventions give different constants for the *same* algorithm. Any convention-dependent factor is meaningless as a property of the algorithm itself. - **The definition absorbs them.** Whatever constant your counting produces disappears into `c`. That is deliberate: it makes the statement a property of the algorithm's *growth*, portable across hardware. ## Why lower-order terms are dropped Because the dominant term eventually dwarfs the rest. In `3n^2 + 50n + 7` at `n = 1,000,000`, the `3n^2` term contributes 3,000,000,000,000 operations while `50n` contributes 50,000,000 — under 0.002% of the total. Asymptotic notation is exactly the discipline of caring about behavior as `n` grows without bound, and in that regime only the fastest-growing term matters. ## What Big-O does not say This is where competent engineers go wrong, so state each direction carefully: - **It is not an operation count.** O(n) does not mean "performs n steps"; it means "performs at most a constant times n steps, eventually". The constant is hidden and can be enormous. - **It predicts nothing at small n.** The bound only takes effect past `n0`, and the hidden constant governs everything before growth dominates. An O(n) algorithm with a big constant genuinely loses to an O(n^2) algorithm on small inputs — which is precisely why mainstream production sort implementations switch to a simple quadratic sort on small runs. Asymptotic superiority is a statement about *sufficiently large* inputs only. - **O(1) does not mean fast.** It means the cost does not grow with `n`. A constant cost of ten million operations is still O(1). - **It is an upper bound, not a tight claim.** Since Big-O only bounds from above, every O(n) function is also O(n^2), O(n^3), and O(2^n) — all formally true, all uselessly loose. The notation family exists to say more when you need to: **Big-Omega** (`Ω`) makes the mirror-image *lower*-bound claim (`f(n) >= c * g(n)` eventually), and **Big-Theta** (`Θ`) makes the two-sided *tight* claim — bounded above and below by constant multiples of the same `g`. When someone says "linear time" and means it exactly, the honest notation is Θ(n). ## The family at a glance | Notation | Claim | Rough analogue | |---|---|---| | `O(g)` | grows no faster than g | `<=` | | `Ω(g)` | grows at least as fast as g | `>=` | | `Θ(g)` | grows exactly as fast as g | `=` | | `o(g)` | grows strictly slower than g | `<` | Everyday speech uses O loosely to mean Θ ("this loop is O(n)" usually intends "exactly linear"). That shorthand is harmless in conversation but the distinction carries real weight in specs, reviews, and proofs — an upper bound can never, by itself, establish that anything is slow.