Big O notation

Big O notation describes how a function grows asymptotically — what an algorithm’s time function looks like for large inputs, ignoring constants and lower-order terms. Writing $f(n)=O(g(n))$ means: for large enough $n$, $f(n)$ is at most a constant times $g(n)$.

Formally:

$f(n)=O(g(n))⟺\exists c>0,n_0>0:\forall n\ge n_0,f(n)\le c\cdot g(n)$

We pick a constant $c$ and a threshold $n_0$. For all inputs bigger than $n_0$, $f$ is bounded above by $c\cdot g$. The constants $c$ and $n_0$ are not unique — many pairs work.

Worked example

Show that $f(n)=8n+128$ is $O(n^2)$.

We need to find $c>0$ and $n_0>0$ such that for all $n\ge n_0$, $8n+128\le c{n}^2$.

Try $c=1$:

$8n+128\le n^2⟺0\le n^2-8n-128⟺0\le (n-16)(n+8)$

Since $n+8>0$ for all $n\ge 0$, the inequality holds when $n-16\ge 0$, i.e. $n\ge 16$.

So for $c=1$ and $n_0=16$, $f(n)\le c{n}^2$ for all $n\ge n_0$. Therefore $f(n)=O(n^2)$.

Note: $f(n)=O(n^2)$ doesn’t mean $f$ grows as fast as $n^2$. It means $f$ grows no faster than $n^2$. In fact $f(n)=8n+128$ is $O(n)$, which is a tighter bound. Both statements are true; the tighter one is more informative.

The big three

Big O is one of three related notations:

• Big O — upper bound. $f(n)=O(g(n))$ means $f$ grows no faster than $g$.
• Big Omega ($\Omega$) — lower bound. $f(n)=\Omega (g(n))$ means $f$ grows at least as fast as $g$.
• Big Theta ($\Theta$) — tight bound. $f(n)=\Theta (g(n))$ means $f$ grows exactly as $g$ (i.e., both $O(g)$ and $\Omega (g)$).

These are bounds on a function’s growth rate; they’re orthogonal to best/worst/average case. You can give a Big-O bound on the worst-case running time (most common), or on the best-case, or on the average-case. The notations describe how a chosen function $f(n)$ scales — not which input you picked $f$ to measure.

In everyday talk “Big O” gets used loosely to mean “tight bound,” but the formal distinction matters when you’re actually doing analysis. See Big Omega notation for lower-bound use (problem complexity arguments) and Big Theta notation for the precise tight-bound notation.

Properties

When combining functions:

• Sum: $f_1(n)+f_2(n)=O(\max (g_1(n),g_2(n)))$. The larger term dominates.
• Product: $f_1(n)\cdot f_2(n)=O(g_1(n)\cdot g_2(n))$. So $O(n^2)\cdot O(n^3)=O(n^5)$.
• Polynomials: $a_k{n}^k+a_{k-1}{n}^{k-1}+\dots +a_0=O(n^k)$. Drop everything but the leading term, drop the leading coefficient.
• Constants: $O(c)=O(1)$ for any constant $c$.

Common growth classes

Ranked from slowest to fastest growth (top is best for an algorithm):

Class	Name	Example
$O(1)$	Constant	Hash table lookup, array indexing
$O(\log n)$	Logarithmic	Binary search, balanced BST operations
$O(n)$	Linear	Linear search, single array traversal
$O(n\log n)$	Linearithmic	Merge sort, quicksort (avg), heap sort
$O(n^2)$	Quadratic	Bubble sort, selection sort, insertion sort
$O(n^3)$	Cubic	Naïve matrix multiply, Floyd-Warshall
$O(2^n)$	Exponential	Brute-force subset enumeration
$O(n!)$	Factorial	Brute-force permutations, traveling salesman

The gap between any two adjacent classes is huge for large $n$. An $O(n)$ algorithm processing 1,000,000 elements might take 1 second; an $O(n^2)$ algorithm on the same input takes 12 days.

Why constants don’t matter

If algorithm A has running time $7n^2$ and algorithm B has running time $2n^2+n$, both are $O(n^2)$. They have the same asymptotic time complexity. For very large $n$, B is roughly $7/2\approx 3.5\times$ faster, but both grow as $n^2$ — and that’s what matters when comparing to a different complexity class.

If algorithm C is $1000n$ (linear with a huge constant), then for small $n$, the $O(n^2)$ algorithms might actually be faster — the constants matter. But for $n>1000/2=500$, C wins, and the gap grows from there. Big O captures eventual behavior, which is usually what dominates.

Worked example: sum function

int sum(int a[], int n) {
    int s = 0;
    for (int i = 0; i < n; i++) {
        s = s + a[i];
    }
    return s;
}

Frequency count by line:

• int s = 0; — 1.
• i = 0 — 1, then i < n runs $n+1$ times (one extra for the failing check).
• s = s + a[i] — runs $n$ times.
• return s; — 1.

Total: $T(n)=1+(n+1)+n+1=2n+3$.

This is $O(n)$ — the constant $2$ and the additive $3$ disappear when we go to Big O. The function grows linearly with the input size.

What Big O isn’t

Two common misunderstandings:

1. Big O isn’t the time taken. It’s the growth rate. Two $O(n)$ algorithms can take very different actual times depending on constants and the specific work per iteration.

2. Big O isn’t a unique answer. Saying $f(n)=O(n^2)$ doesn’t preclude $f(n)=O(n)$ or $f(n)=O(n^3)$. They’re all valid upper bounds; the tightest one is most useful.

When someone says “the algorithm is $O(n\log n)$,” they almost always mean it’s tightly $\Theta (n\log n)$ — but they’re informally using the more familiar Big O. Context disambiguates.