Big-O Notation

Big-O notation gives an upper bound on how a function grows, ignoring constants and low-order terms.

What it captures

Big-O describes the worst-case growth rate of a function as its input size increases. We write f(n) = O(g(n)) to mean that beyond some input size, f(n) never exceeds a constant multiple of g(n). It answers "how does the cost scale" rather than "exactly how many steps."

The 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. The constant c absorbs implementation details; n0 lets us ignore small inputs where behavior is irregular.

Why constants are dropped

An algorithm doing 3n + 50 steps and one doing 1000n steps are both O(n): they scale linearly. On large inputs the scaling dominates any fixed factor. Big-O deliberately discards constants so that comparisons reflect fundamental behavior, not hardware or coding style.

Common growth rates

O(1): constant, independent of input size
O(log n): logarithmic, halving each step (binary search)
O(n): linear, one pass
O(n log n): sorting by comparison
O(n^2): nested loops over the input
O(2^n): exponential, doubling per added element

A worked example

python

# O(n^2): for each element, scan all others
def has_duplicate(a):
    for i in range(len(a)):
        for j in range(i+1, len(a)):
            if a[i] == a[j]:
                return True
    return False

The nested loops run about n^2/2 comparisons, so the cost is O(n^2). A hash-set version does one pass, O(n), which scales far better on large arrays.

How to read it honestly

Big-O is an upper bound, not a promise of tightness. Saying an algorithm is O(n^2) does not forbid it also being O(n). For a two-sided description use big-Theta. For lower bounds use big-Omega.