Big O Notation

Formal definition

$f(n) = O(g(n))$ means there exist constants $c$ and $n_0$ such that:

$|f(n)| \leq c \cdot |g(n)| \quad \text{for all } n \geq n_0$

In plain English: $|f(n)|$ is bounded above by some constant multiple of $|g(n)|$ for all sufficiently large n.

What Big O captures

The notation abstracts away details that do not affect asymptotic growth:

• Constant factors: $100n^2$ will beat $n^3$ in the long run. Constants depend on hardware, OS, and language — ignoring them makes comparisons broadly valid.
• Insignificant terms: If cost is $n^2 + 99n + 900$, the $n^2$ term eventually dominates. The $99n$ term is bigger for $n < 99$, but $n^2$ overtakes it.
• Small values of n: The role of $n_0$ in the definition is to ignore finitely many exceptions where the bound does not hold.

Simple facts

Constant factors and insignificant terms disappear:

$O(2g(n)) \text{ is the same as } O(g(n))$ $O(\log_{10} n) \text{ is the same as } O(\ln n)$ $O(n^2 + 50n + 36) \text{ is the same as } O(n^2)$

For the last one: $n^2 + 50n + 36 \leq 2n^2$ for $n \geq 51$, so we can double the constant factor and drop the lower-order terms.

Containment relationships

If $c$ and $d$ are constants with $0 < c < d$, then:

• $O(n^c) \subset O(n^d)$
• $O(c^n) \subset O(d^n)$
• $O(\log n) \subset O(n^c)$

The notation $O(f(n)) \subset O(g(n))$ means that if a function is $O(f(n))$, it is also $O(g(n))$ — the former gives a tighter bound. For example, if $f(n) = O(2^n)$ then trivially $f(n) = O(3^n)$, but the converse does not hold.

Why constant factors are ignored

• They seldom make a difference asymptotically: $100n^2$ beats $n^3$ for large n
• They are unstable: different hardware, operating system, or language changes them
• Ignoring them allows comparisons that remain valid across many circumstances

Limitations of Big O

Even ignoring constant factors, measurement units matter. Multiplication may be treated as one unit of cost, but multiplying two n-digit numbers for large n is itself expensive (relevant for cryptography). Few things are truly O(1): storing the number n requires O(log n) bits. An O(1) cost usually assumes operations fit within standard hardware arithmetic capacity.