Neel Mishra
← All Posts
DSA Series · Complexity · Part 1

Introduction to Big-O

March 2026 · 20 min read

Before we can compare algorithms, we need a language for describing their cost. Big-O notation is that language. It tells us how an algorithm's running time or memory usage scales as the input grows, ignoring machine-specific details like clock speed, cache size, or compiler optimizations.

Why We Need Big-O

Imagine two sorting algorithms. On your machine, Algorithm A sorts 1000 numbers in 2ms and Algorithm B takes 3ms. A is faster, right? Maybe not,

For $n = 1000$, A wins because $c_1$ is small. But for $n = 10^6$, A takes $c_1 \cdot 10^{12}$ operations while B takes $c_2 \cdot 2 \times 10^7$. B is now 50,000× faster.

Big-O captures this by stripping away the constants $c_1, c_2$ and focusing on the growth rate: $O(n^2)$ vs $O(n \log n)$. The growth rate tells you which algorithm wins as $n \to \infty$.

The RAM Model

To count "operations," we need a model of computation. The Random Access Machine (RAM) model assumes:

This is a simplification (real CPUs have caches, pipelines, branch prediction), but it's accurate enough for algorithm analysis. The RAM model lets us count operations and derive growth rates without worrying about hardware.

Counting Operations

Example 1: Linear Search

int linearSearch(vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {   // loop: runs n times
        if (arr[i] == target)                  // 1 comparison
            return i;                          // 1 return
    }
    return -1;
}

Best case: Target is at index 0. We do 1 comparison. Cost: $1 = O(1)$.

Worst case: Target isn't in the array. We do $n$ comparisons. Cost: $n = O(n)$.

Average case: Target is equally likely at any position. Expected comparisons: $\frac{1}{n}\sum_{i=1}^{n} i = \frac{n+1}{2} = O(n)$.

In all three analyses, the growth rate is the same (well, best case is $O(1)$ but we usually report worst case). The key: the loop runs proportional to n.

Example 2: Nested Loops

void allPairs(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {         // outer: n iterations
        for (int j = 0; j < n; j++) {     // inner: n iterations each
            process(arr[i], arr[j]);       // 1 operation
        }
    }
}

Total operations: $n \times n = n^2$. This is $O(n^2)$.

Example 3: Dependent Loops

void triangular(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {     // inner runs 0, 1, 2, ..., n-1 times
            process(arr[i], arr[j]);
        }
    }
}

Total operations:

$$\sum_{i=0}^{n-1} i = 0 + 1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2} = \frac{n^2 - n}{2}$$

Drop the lower-order term and constant: $\frac{n^2 - n}{2} = O(n^2)$.

Even though this does roughly half the work of the full $n \times n$ nested loop, both are $O(n^2)$. Big-O ignores constant factors.

The Formal Definition

Definition: We say $f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0 \geq 0$ such that: $$f(n) \leq c \cdot g(n) \quad \text{for all } n \geq n_0$$

In English: $f(n)$ is $O(g(n))$ if, beyond some threshold $n_0$, $f(n)$ is at most a constant multiple of $g(n)$.

Proof Example: $3n^2 + 5n + 7 = O(n^2)$

We need to find $c$ and $n_0$ such that $3n^2 + 5n + 7 \leq c \cdot n^2$ for all $n \geq n_0$.

For $n \geq 1$: $5n \leq 5n^2$ and $7 \leq 7n^2$. So:

$$3n^2 + 5n + 7 \leq 3n^2 + 5n^2 + 7n^2 = 15n^2$$

Choose $c = 15$ and $n_0 = 1$. ✔

Proof Example: $n^2 \neq O(n)$

Assume for contradiction that $n^2 \leq c \cdot n$ for all $n \geq n_0$. Then $n \leq c$, which fails for $n > c$. Contradiction. ✔

The Drop Rules

These follow directly from the definition and make Big-O practical:

Rule 1: Drop constants

$5n = O(n)$, $100n^2 = O(n^2)$, $0.001 \cdot 2^n = O(2^n)$.

Why: The constant $c$ in the definition absorbs any multiplicative constant.

Rule 2: Drop lower-order terms

$n^2 + n = O(n^2)$, $n^3 + n^2 + n = O(n^3)$, $2^n + n^{100} = O(2^n)$.

Why: For large $n$, the highest-order term dominates. Formally, $n / n^2 \to 0$ as $n \to \infty$, so $n$ is negligible compared to $n^2$.

Rule 3: Sum rule

If you do task A in $O(f(n))$ then task B in $O(g(n))$ sequentially:

$$O(f(n)) + O(g(n)) = O(\max(f(n), g(n)))$$

Rule 4: Product rule

If you do task A $O(f(n))$ times, each taking $O(g(n))$:

$$O(f(n)) \times O(g(n)) = O(f(n) \cdot g(n))$$

Deriving Complexity from Code

Here's a systematic approach:

  1. Simple statements (assignments, arithmetic, comparisons): $O(1)$.
  2. Sequential blocks: Add the costs. Take the max (sum rule).
  3. Loops: Cost = (number of iterations) × (cost per iteration).
  4. Nested loops: Multiply the iteration counts (product rule).
  5. Conditionals: Cost = cost of the more expensive branch (worst case).
  6. Function calls: Replace the call with the function's cost and simplify.
  7. Recursion: Write a recurrence relation and solve it (covered in Part 4).

Practice: What's the complexity?

void mystery(int n) {
    for (int i = 1; i < n; i *= 2) {    // how many iterations?
        for (int j = 0; j < n; j++) {    // n iterations
            doWork();                      // O(1)
        }
    }
}

The outer loop: $i$ takes values $1, 2, 4, 8, \ldots$ until $i \geq n$. That's $\lfloor \log_2 n \rfloor + 1$ iterations. The inner loop runs $n$ times for each outer iteration.

$$T(n) = \log_2 n \times n = O(n \log n)$$

Practice: Tricky dependent loop

void tricky(int n) {
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j += i) {  // step size = i
            doWork();
        }
    }
}

For each $i$, the inner loop runs $\lfloor n/i \rfloor$ times. Total:

$$T(n) = \sum_{i=1}^{n-1} \frac{n}{i} = n \sum_{i=1}^{n-1} \frac{1}{i} = n \cdot H_{n-1} \approx n \ln n = O(n \log n)$$

Here $H_n$ is the $n$-th harmonic number, which is $\Theta(\ln n)$. This pattern appears in algorithms like the Sieve of Eratosthenes.

Best, Worst, and Average Case

Big-O describes the upper bound on growth, not which input you're analyzing. You can have:

When someone says "this algorithm is $O(n \log n)$" without qualification, they almost always mean worst-case. If they mean average case, they'll say so explicitly.

AlgorithmBestAverageWorst
Linear search$O(1)$$O(n)$$O(n)$
Binary search$O(1)$$O(\log n)$$O(\log n)$
Insertion sort$O(n)$$O(n^2)$$O(n^2)$
Quicksort$O(n \log n)$$O(n \log n)$$O(n^2)$
Merge sort$O(n \log n)$$O(n \log n)$$O(n \log n)$

Common Pitfalls

Summary