Big-O Notation

Definition: A mathematical notation used to describe the upper bound of an algorithm’s execution time or memory usage in terms of input size (n).

How It Works

Big-O describes asymptotic behavior: how an algorithm’s cost grows as input size n grows toward infinity. It deliberately ignores behavior on small inputs and ignores constant factors, because those effects get dominated as n grows large enough.

Formal definition: f(n) = O(g(n)) if there exist positive constants c and n0 such that f(n) <= c * g(n) for all n >= n0. In plain terms: past some threshold input size, g(n) (scaled by a constant) is always an upper bound on the actual cost f(n). This is why O(3n^2 + 5n + 10) simplifies to O(n^2): pick c = 18 and the quadratic term alone eventually dominates every lower-order term combined.

Common complexity classes, ranked from best to worst for large n:

Notation	Name	Example
O(1)	Constant	Array index access
O(log n)	Logarithmic	Binary Search
O(n)	Linear	Single pass scan
O(n log n)	Linearithmic	MergeSort, HeapSort
O(n^2)	Quadratic	Nested loop, bubble sort
O(2^n)	Exponential	Naive recursive subset generation
O(n!)	Factorial	Brute-force traveling salesman

Sibling notations complete the picture and are frequently confused with Big-O itself:

Big-Omega (Ω) describes a lower bound: the algorithm takes at least this long in the best case.
Big-Theta (Θ) describes a tight bound: both an upper and lower bound meet, meaning the algorithm’s growth rate is exactly characterized, not just capped.
Small-o describes a strict, non-tight upper bound (the function grows strictly slower, never matching), used less often in casual engineering discussion but common in formal algorithm analysis papers.

Big-O applies equally to time and space complexity. Space complexity must account for all auxiliary memory used beyond the input itself, including recursion call stack frames, which is why a recursive algorithm can have higher space complexity than an iterative one solving the exact same problem.

Complexity Growth in Practice

For an input of size n = 1,000,000, here’s roughly how many “steps” each class implies:

Complexity	Approximate steps at n = 1,000,000
O(1)	1
O(log n)	~20
O(n)	1,000,000
O(n log n)	~20,000,000
O(n^2)	1,000,000,000,000

The jump from O(n log n) to O(n^2) is the practical line between “runs in seconds” and “doesn’t finish” for large real-world datasets, which is exactly why interview and code-review discussions treat that boundary as significant.

Deriving Big-O From Code, Step by Step

def has_duplicate_pair(arr, target_sum):     # arr has n elements
    for i in range(len(arr)):                # runs n times
        for j in range(i + 1, len(arr)):     # runs up to n times per i
            if arr[i] + arr[j] == target_sum:
                return True
    return False

Count the work: the outer loop runs n times; for each outer iteration, the inner loop runs roughly n - i times. Summing (n-1) + (n-2) + ... + 1 + 0 gives n*(n-1)/2, which simplifies to O(n^2) after dropping the constant factor and lower-order term. A one-line rewrite using a hash set changes this analysis entirely:

def has_duplicate_pair(arr, target_sum):
    seen = set()
    for x in arr:                            # single pass, n iterations
        if target_sum - x in seen:           # O(1) average hash set lookup
            return True
        seen.add(x)
    return False

Now there’s one loop of n iterations, each doing O(1) average work, giving O(n) time at the cost of O(n) extra space, exactly the kind of time-space tradeoff Big-O analysis makes explicit and comparable.

Why It Matters

Allows developers to compare algorithmic efficiency independent of hardware, compiler, and language, giving a shared vocabulary that survives across implementations.
Crucial for selecting scalable solutions: an O(n^2) algorithm that “works fine” on 1,000 rows in a test environment can take hours on 10 million rows in production, and Big-O is what predicts that failure before it happens.
Underpins technical interviews and code review discussions as the standard shorthand for reasoning about scalability before code ships, letting reviewers flag a risky pattern (like a nested loop over a growing dataset) without profiling it first.

Common Pitfalls

Ignoring constant factors when n is small: an O(n^2) insertion sort with tiny constants can beat an O(n log n) merge sort for n below roughly 50, which is exactly why hybrid sorts like Timsort and Introsort fall back to insertion sort on small partitions.
Confusing worst-case Big-O with average-case: QuickSort is O(n log n) on average but O(n^2) worst-case on already-sorted input with a naive first-element pivot.
Treating amortized complexity, like dynamic array append, as if every single operation is guaranteed that cost, rather than the cost averaged over a long sequence of operations.
Forgetting hidden costs inside library calls: Python’s list.pop(0) is O(n), not O(1), because it has to shift every remaining element left by one.
Quoting Big-O without specifying which case (best, average, worst) it refers to, which makes the number nearly meaningless for algorithms whose behavior varies wildly by input shape.

Comparison

Notation	Bound Type	Answers	Typical Use
O(g(n))	Upper bound	“At most this slow”	Worst-case guarantees
Ω(g(n))	Lower bound	“At least this slow”	Best-case floor
Θ(g(n))	Tight bound	“Exactly this order”	Precise growth characterization
o(g(n))	Strict upper bound	“Strictly slower than”	Formal proofs, rarely used casually

Example

Searching an unsorted array of size n sequentially takes O(n) time in the worst case, whereas accessing an element by index takes O(1) time. Concretely, for n = 1,000,000: a linear scan needs up to 1,000,000 comparisons in the worst case, Binary Search on sorted data needs at most about 20 (log2 1,000,000 ≈ 19.9), and a Hash Table lookup needs roughly 1 comparison on average. This is the entire practical argument for sorting data or building an index before doing repeated lookups: the upfront O(n log n) sort cost is repaid many times over once lookups drop from O(n) to O(log n) or O(1).

Real-World Systems

Python’s official documentation publishes a “TimeComplexity” wiki page listing the Big-O of every list, dict, and set operation, treated as a load-bearing part of the language’s public contract, not just an implementation detail.
Query planners in databases like PostgreSQL estimate the cost of candidate execution plans (sequential scan vs. index scan vs. hash join) using cost models built on the same asymptotic reasoning: an index scan’s O(log n) lookup beats a sequential scan’s O(n) once table size crosses a threshold the planner estimates from table statistics.
Job postings and technical interviews at most large software companies explicitly grade candidates on stating and justifying the Big-O of their solutions, making it one of the few pieces of CS theory with direct, universally recognized hiring impact.

FAQ

Does Big-O tell you the actual running time? No. It tells you the growth trend, not the wall-clock time. An O(n) algorithm with a huge constant factor can be slower than an O(n log n) algorithm on realistic input sizes; Big-O only becomes decisive as n grows large enough for the constants to stop mattering.

Why do people say “Big-O” when they mean “Big-Theta”? Informally, most engineers use O(n) to mean “this algorithm’s cost is on the order of n,” which is really a tight (Theta) claim. Strictly, O(n) only claims an upper bound, so O(n^2) is technically also a true (if less useful) statement about a linear algorithm. The looser usage is common enough in industry that it rarely causes confusion, but it’s worth knowing the precise distinction exists.

How do you determine the Big-O of code with multiple loops? Sequential loops add: two separate O(n) loops back to back are still O(n). Nested loops multiply: a loop inside a loop, each running n times, is O(n^2). Recursive calls need their own analysis via a recurrence relation, often solved with the Master Theorem.

Common Interview Questions

What’s the difference between O(n) and Θ(n)? — O(n) is an upper bound only; Θ(n) claims the growth rate is both upper- and lower-bounded by n, i.e. exactly linear.
Why is an O(n log n) sort considered “optimal” for comparison-based sorting? — because a comparison sort must resolve n! possible orderings, and the decision-tree argument shows any comparison-based algorithm needs at least log2(n!) ≈ n log n comparisons in the worst case.
Can an algorithm have different time and space complexity? — yes, routinely; memoized recursion often trades higher O(n) space for lower time compared to a naive O(2^n) recursive version with no extra space.
Is O(1) always faster than O(n)? — not for small n, since O(1) can hide a large constant while O(n) can have a tiny one; the crossover point depends entirely on the constants involved.
How would you determine an unknown function’s Big-O empirically? — measure runtime at several increasing input sizes and check how the ratio between successive runtimes scales, e.g. doubling n and seeing runtime roughly double (linear) versus quadruple (quadratic).

Referenced by

Dig deeper

Spot an error in this note?