Big-O Notation

Big-O is the language we use to describe how an algorithm’s running time (or memory) grows as the input grows large, while ignoring constant factors and slower-growing terms. Formally — following CLRS Ch. 3.1 — O(g(n)) is the set of functions f such that there exist positive constants c and n₀ with 0 ≤ f(n) ≤ c·g(n) for every n ≥ n₀ (per CLRS Ch. 3). When we write T(n) = O(n²), we are claiming that, for inputs above some threshold, the actual running time is at most a constant multiple of n². Big-O is only an upper bound; the matching lower-bound and tight-bound notations — Ω and Θ — are covered in Big-Omega and Big-Theta.

1. Intuition — The Stack of Tests Analogy

Imagine you are a teacher who needs to grade a stack of n test papers.

• If you only need to check that the stack is not empty, you do one peek — your work doesn’t grow with the stack height. We call this constant time, written O(1).
• If you need to grade every test once, you do n units of work — work grows proportionally to the input. We call this linear time, O(n).
• If you need to compare every test to every other test (e.g., to check for duplicates by brute force), you do roughly n × n = n² comparisons — quadratic time, O(n²).
• If you need to sort the tests using a smart strategy like merge sort, you do roughly n × log n work — linearithmic time, O(n log n).

Big-O captures the shape of the curve “work vs. input size,” not the exact number of operations. A very fast O(n²) implementation can beat a sloppy O(n) for small inputs — but for large enough inputs, the O(n) always wins. Big-O is about the long-term shape.

2. The Formal Definition — Symbol by Symbol

CLRS gives the definition as a set of functions (Ch. 3.1):

O(g(n)) = { f(n) : there exist positive constants c and n₀
                   such that 0 ≤ f(n) ≤ c · g(n) for all n ≥ n₀ }

We almost always write f(n) = O(g(n)) rather than the set-membership form f(n) ∈ O(g(n)); CLRS calls this “abuse of equality” and notes it is the established convention. Substantively the two notations mean the same thing.

Walking the definition symbol by symbol:

• f(n) is the function we are bounding — typically the running time T(n) of an algorithm on an input of size n.
• g(n) is the function we are bounding against — a simple growth rate like n, n log n, or n².
• “There exist positive constants c and n₀” — the existential quantifier ∃c > 0, ∃n₀ > 0. Some such pair must exist; we get to pick them when proving the bound. They are constants in the sense that they do not depend on n.
• “For all n ≥ n₀” — the universal quantifier ∀n ≥ n₀. Once we are past the threshold n₀, the inequality must hold for every further input size.
• “0 ≤ f(n) ≤ c · g(n)” — two inequalities at once. The left inequality says f is asymptotically non-negative (CLRS requires this — it tames pathological negative running-time functions and is consistent with T(n) being measured in operations). The right inequality is the substantive claim: f does not exceed a constant multiple of g past the threshold.

In a single line of quantifiers:

f(n) = O(g(n))  ⇔  ∃ c > 0, ∃ n₀ ∈ ℕ, ∀ n ≥ n₀ : 0 ≤ f(n) ≤ c · g(n).

The two pieces do specific work:

• The constant c lets us ignore implementation-detail multipliers. A 2n operation count is still O(n); the 2 is absorbed by choosing c = 2.
• The threshold n₀ lets us ignore behavior at small inputs, where lower-order terms or one-off setup costs might dominate. We only care about eventually.

Two properties follow immediately. First, the definition is not tight: if f(n) = n then f(n) = O(n²) is true (pick c = 1, n₀ = 1: n ≤ n² for all n ≥ 1), even though f is wildly smaller than n². Second, by transitivity (CLRS p. 49), f = O(g) and g = O(h) imply f = O(h) — useful when chaining bound claims.

3. Historical Note — Where the Notation Came From

The O symbol — what mathematicians sometimes call big-omicron — was introduced by Paul Bachmann in 1894 in Analytische Zahlentheorie and popularised by Edmund Landau, hence the older name Bachmann–Landau notation (Wikipedia, Big O notation). It lived in analytic number theory for nearly a century before Donald Knuth dragged it into algorithm analysis. In his 1976 SIGACT News paper Big Omicron and big Omega and big Theta, Knuth complained that computer scientists were misusing O to mean tight bound and introduced the matching Ω (lower bound) and Θ (tight bound) to give complexity analysts the vocabulary they actually needed. Knuth’s Ω is not the older Hardy–Littlewood Ω used in number theory — see Big-Omega and Big-Theta §5 for the distinction.

CLRS adopts the Knuth convention throughout and is explicit that in their book, O is only an upper bound: “Distinguishing asymptotic upper bounds from asymptotically tight bounds has now become standard in the algorithms literature” (Ch. 3.1).

4. The Common Growth Rates (Memorize This Table)

Sorted from fastest-growing-is-worst to slowest-growing-is-best:

Notation	Name	n=10	n=100	n=1000	Example algorithm
O(1)	constant	1	1	1	Hash-table lookup (average), array index
O(log n)	logarithmic	~3	~7	~10	Binary Search
O(√n)	square-root	~3	10	~32	Trial-division primality
O(n)	linear	10	100	1,000	Linear Search, single array pass
O(n log n)	linearithmic	~33	~664	~9,966	Merge Sort, Quicksort avg, heap-sort
O(n²)	quadratic	100	10,000	1,000,000	Bubble/insertion/selection sort, all-pairs brute-force
O(n³)	cubic	1,000	10⁶	10⁹	Floyd-Warshall, naive matrix multiplication
O(2ⁿ)	exponential	1,024	~10³⁰	absurd	Brute-force subset enumeration
O(n!)	factorial	~3.6M	~10¹⁵⁸	absurd	Brute-force permutations (e.g., naive TSP)

Why the gap matters: doubling the input size barely affects an O(log n) algorithm but quadruples the time of an O(n²) one and squares the time of an O(2ⁿ) one. The curve shape determines whether your algorithm scales.

5. The Three Rules of Simplifying

When you analyze code, you start with an exact operation count, then simplify in three steps:

Rule 1 — Drop Multiplicative Constants

If your loop does 5n + 3 work, that is O(n). The 5 and 3 are absorbed into the unspecified constant c.

Why this rule is valid: the constant depends on machine speed, language, compiler, cache behavior — none of which are intrinsic to the algorithm. Big-O captures the algorithm, not the hardware.

Rule 2 — Drop Slower-Growing Terms

O(n² + n) simplifies to O(n²). As n grows large, the n becomes negligible compared to n².

For n = 1000: n² = 1,000,000 and n = 1,000. The n is 0.1% of the total — a rounding error.

Rule 3 — Different Variables Stay Separate

If your algorithm processes a set of size n against a set of size m, and you can’t say which dominates, write O(n + m) or O(nm) — do not collapse into O(n). The two sizes might grow independently. CLRS Exercise 3.1-8 generalises the definition to multiple parameters explicitly.

Common mistake

Writing O(n) when you mean O(n + m) is a real interview ding when m is something like “the number of edges” and n is “the number of nodes” — those grow very differently in dense vs. sparse graphs.

6. A Tiny Worked Example

Consider this code:

def f(arr):                  # arr has length n
    total = 0                # 1 op
    for x in arr:            # n iterations
        total += x           #   1 op
    for i in range(len(arr)):       # n iterations
        for j in range(len(arr)):   #   n iterations each
            print(i, j)             #     1 op
    return total             # 1 op

Counting:

• Initialization and return: 1 + 1 = 2 ops (constant)
• First loop: n ops
• Nested loop: n × n = n² ops

Total: T(n) = n² + n + 2

Simplify:

• Drop constant 2 (Rule 2)
• Drop slower-growing n (Rule 2)
• We are left with n², no constants in front to drop

Answer: T(n) = O(n²).

Formal verification. To rigorously discharge the definition we must produce c, n₀. Choose c = 3, n₀ = 2: for n ≥ 2 we have n² + n + 2 ≤ n² + n² + n² = 3n². So T(n) ≤ 3n² for all n ≥ 2 — the existential is witnessed, the bound holds.

7. Pseudocode for Operation Counting

analyze(code):
    if code is a single statement:
        return O(1)
    if code is a sequence A; B:
        return O(analyze(A)) + O(analyze(B))   # take the bigger
    if code is a loop running k times with body B:
        return k * analyze(B)
    if code is a recursive call:
        write a recurrence T(n) = ... and solve it (see [[Master Theorem]])

The only tricky case is recursion — that’s what the Master Theorem and Recurrence Relations notes exist for.

8. Big-O vs Big-Ω vs Big-Θ — The Trio

Big-O is one of three closely-related asymptotic notations:

• f(n) = O(g(n)) — g is an upper bound (eventually). “f grows no faster than g.”
• f(n) = Ω(g(n)) — g is a lower bound. “f grows at least as fast as g.”
• f(n) = Θ(g(n)) — g is both. “f grows exactly as fast as g (up to constants).”

CLRS Theorem 3.1 makes the relationship explicit: f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).

The casual-usage convention. In interview talk, and even in much published literature, people say “Big-O” when they mean “tight bound” (Θ). Strictly, an algorithm claimed as O(n²) could secretly run in O(n) — Big-O is only an upper bound and is not falsified by a faster reality. The Educative survey of Misuses of Big-O notation calls this conflation out explicitly: “People often interchange Big-O and Theta (Θ) notation, which changes the meaning of the obtained runtime.” The convention is widely observed because in practice the speaker has analysed the algorithm carefully enough to know the bound is tight, and O is the symbol everyone learned first. When precision matters — for example, a senior interviewer probing whether you actually understand the algorithm — state Θ. See Big-Omega and Big-Theta for the strict treatment.

9. Worst Case, Average Case, Best Case

T(n) is not a single number for a given n — it depends on the specific input. So we describe complexity in three flavors:

• Worst case — the slowest input of size n. O(...) notation usually refers to this when said without qualification. This is what interviews care about most.
• Average case — average over all inputs (or some assumed distribution). Used when worst case is rare and pessimistic, e.g., quicksort’s O(n log n) average vs O(n²) worst.
• Best case — the luckiest input. Mostly trivia; rarely useful unless the algorithm is adaptive (insertion sort is O(n) best case on already-sorted input).

A separate axis is amortized complexity — averaging cost over a sequence of operations rather than a single one. Amortized analysis is a different question from worst/average/best because it bounds the total cost of m operations, not a single one. The canonical example is a dynamic array (std::vector, Python list): a single push_back can be O(n) if it triggers a reallocation, but the amortized cost per push_back is O(1) because reallocations are rare. See Amortized Analysis for the aggregate, accounting, and potential methods of proving such bounds.

10. Space Complexity — Same Notation, Different Resource

Big-O also describes memory growth, called space complexity.

• Auxiliary space — extra memory the algorithm uses beyond the input.
• Total space — auxiliary plus input.

Interviews usually mean auxiliary space. Examples:

• Merge Sort: O(n) auxiliary (the merge buffer)
• In-place Quicksort: O(log n) auxiliary (recursion stack only) — but worst-case O(n) if pivots are unbalanced
• Binary Search (iterative): O(1) auxiliary
• Binary Search (recursive): O(log n) auxiliary (stack frames)

Recursion always costs stack space. The recursion stack itself is part of space complexity. A recursive function with depth d uses O(d) auxiliary space.

11. The Pitfalls Section (Interview-Critical)

11.1 Confusing Time and Space

O(n) time does not imply O(n) space. A two-pointer algorithm is often O(n) time and O(1) space. Always state both.

11.2 Hidden Constants That Bite

Two algorithms both O(n log n) can differ by 10× in real wall-clock time:

• A cache-friendly merge sort vs. a pointer-chasing one
• Quicksort’s tight inner loop vs. heap sort’s pointer-juggling

Big-O does not say which is fastest in practice. It says which scales. Don’t claim algorithm X is “faster” — claim it’s “asymptotically faster” or “faster for large n.”

11.3 Mistaking Logarithm Bases

log₂ n, log₁₀ n, ln n differ only by a constant factor (log_b n = log_a n / log_a b). So O(log n) doesn’t specify a base — they’re all the same big-O class. Don’t write O(log₂ n) — the base is meaningless in Big-O.

11.4 The “n + m” Trap

Common in graph problems. If you see “graph with V vertices and E edges,” BFS/DFS is O(V + E), not O(V) or O(E). Both terms matter; for a sparse graph E ≈ V, but for a dense graph E ≈ V².

11.5 Treating Hash Table as Truly O(1)

Hash Table operations are average-case O(1) (assuming simple uniform hashing) and worst-case O(n) (when every key collides into one chain). The standard interview phrasing is “O(1) average case, O(n) worst case” — say both. The word “amortized” is sometimes added because table resizing during growth is O(n) once in a while but O(1) amortized across inserts; that is a separate amortization argument from the per-lookup analysis.

11.6 Counting Wrong Loops

for i in range(n):       # n iterations
    for j in range(i):   # i iterations — varies!
        do_thing()

Total work is 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²), not O(n). The inner loop’s average size is n/2, but the total is still quadratic.

This is the most-failed analysis question in junior interviews.

11.7 “At Least Big-O” Is Nonsense

CLRS Exercise 3.1-3 makes this point explicitly: the statement “the running time of algorithm A is at least O(n²)” is meaningless. O(n²) is itself an upper bound, so “at least an upper bound” parses to no constraint at all — every function is “at least” bounded above by something. If you mean “the running time is at least n²,” you mean Ω(n²), not “at least O(n²).” This catches even strong candidates because the phrasing sounds reasonable.

12. Worked Recurrence Example — Why O(n) Build-Heap Is Possible

Some Big-O results are surprising and come out of summation analysis. The O(n) cost of building a binary heap from an unsorted array is the canonical example.

Naive intuition: “n inserts, each O(log n) — so it’s O(n log n).”

Tighter analysis: when you sift-down from the bottom up, most nodes are near the bottom and have very short sift paths. Specifically, in a heap of size n:

• ~n/2 nodes at depth h from the bottom = 0 → cost 0
• ~n/4 nodes with depth-from-bottom 1 → cost 1
• ~n/8 nodes with depth-from-bottom 2 → cost 2
• …

Total = Σ (n/2^(k+1)) · k for k = 0 to log n. This sum converges to n (geometric series with Σ k/2^k = 2). So heap build is O(n), not O(n log n).

The lesson: don’t multiply naive worst-cases when the per-operation cost varies — sum the actual costs.

13. When Big-O Is Not Enough

Big-O is silent about:

• Constants — important for small n. A O(n²) algorithm with a tiny constant can beat O(n log n) for n < 100.
• Cache behavior — a “cache-oblivious” merge sort can beat a theoretically equal heap sort by 5×.
• Concurrency — Big-O is sequential by default. A parallelizable O(n log n) may dominate a sequential O(n) on real hardware.
• I/O — for external-memory algorithms, block-transfer count matters more than instruction count. See B-Tree for the canonical example.

For interviews, this nuance is usually only relevant if you’re being asked about real-world performance. Default to “what is the asymptotic complexity?” answers.

14. Diagram — The Growth Curves

flowchart LR
    A[Input size n] --> B
    B[O(1)] --> O1[Flat line]
    A --> C[O(log n)]
    C --> O2[Slowly rising]
    A --> D[O(n)]
    D --> O3[Diagonal line]
    A --> E[O(n log n)]
    E --> O4[Slightly above diagonal]
    A --> F[O(n²)]
    F --> O5[Steep parabola]
    A --> G[O(2^n)]
    G --> O6[Wall — explodes after small n]

What this diagram shows. Schematic of how each complexity class scales as n grows. The visual takeaway: O(2ⁿ) and worse become unusable past n ≈ 30; O(n²) becomes painful past n ≈ 10,000; O(n log n) and below remain practical for very large inputs (n in the millions and beyond).

15. Interview Soundbites

When asked “what’s the complexity of your solution?” the format is:

“Time is O(<expr>) because <one-sentence reasoning, e.g. ‘we visit each element of the array exactly twice’>. Space is O(<expr>) because <one-sentence reasoning, e.g. ‘we keep a hash map of size at most n’>.”

Always state both. Always justify in one sentence. Never say “O(n)” without naming what n is. If you know the bound is tight, say Θ — see Big-Omega and Big-Theta §8 for when to drop the casual-usage convention.

16. See Also

• Big-Omega and Big-Theta — the strict definitions of lower and tight bounds, and the little-o/little-ω strict variants
• Master Theorem — solving divide-and-conquer recurrences
• Amortized Analysis — averaging cost over operation sequences (a different axis from worst/avg/best)
• Recurrence Relations — setting up and solving recurrences from code
• Space Complexity — auxiliary vs total memory
• SWE Interview Preparation MOC