Big O Notation

Big O notation is a way of describing how fast an algorithm's running time or memory usage grows as the input size increases. It focuses on the dominant term and ignores constants, giving you a broad picture of efficiency rather than an exact count of operations.

Big O notation provides an upper bound on the growth rate of a function. Formally, we say $f(n) \in O(g(n))$ if there exist positive constants $c$ and $n_0$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$ . In computer science, $f(n)$ typically represents the number of operations an algorithm performs on an input of size $n$ , and $g(n)$ is a simpler function that captures the dominant growth behavior. Because Big O describes a worst-case upper bound, it strips away lower-order terms and constant factors.

Key Formula

f(n) \in O(g(n)) \iff \exists\, c > 0,\; n_0 > 0 \;\text{ such that }\; f(n) \leq c \cdot g(n) \;\text{ for all }\; n \geq n_0

Where:

$f(n)$ = the actual growth function of the algorithm (e.g., number of operations)
$g(n)$ = the simpler bounding function (e.g., n², n log n)
$c$ = a positive constant multiplier
$n_0$ = the input size beyond which the bound holds

Worked Example

Problem: An algorithm performs f(n) = 3n² + 12n + 5 operations for an input of size n. What is its Big O classification?

Step 1: Identify all terms in the expression.

f(n) = 3n^2 + 12n + 5

Step 2: Find the dominant term — the one that grows fastest as n gets large. Here,

3n^2

grows faster than

12n

5

\text{Dominant term: } 3n^2

Step 3: Drop the constant coefficient. Big O ignores constant multipliers because it cares about the rate of growth, not the exact count.

3n^2 \rightarrow n^2

Step 4: Write the result in Big O notation.

f(n) \in O(n^2)

Answer: The algorithm is

O(n^2)

, meaning its running time grows roughly in proportion to the square of the input size.

Visualization

Why It Matters

When you're choosing between algorithms, Big O notation tells you which one will scale better as the problem gets larger. A search algorithm that is

O(\log n)

will vastly outperform one that is

O(n)

when dealing with millions of records. Software engineers, data scientists, and anyone designing systems use Big O daily to predict performance and avoid bottlenecks.

Common Mistakes

Mistake: Keeping constant coefficients in the final answer, e.g., writing

O(3n^2)

instead of

O(n^2)

Correction: Big O drops constant multipliers because they don't affect the growth rate category. Always simplify to the bare term:

O(n^2)

, not

O(3n^2)

Mistake: Including lower-order terms, e.g., writing

O(n^2 + n)

instead of

O(n^2)

Correction: For large

n

, the lower-order terms become negligible compared to the dominant term. Keep only the fastest-growing term:

O(n^2)

Related Terms

Algorithm — Big O measures an algorithm's efficiency
Function — Big O compares growth rates of functions
Limit — Formal Big O definition uses limit-like reasoning