What Is Big O Notation? (Explained with Real Examples)

Short answer

Big O notation describes how an algorithm's time or memory usage grows as the input size grows. O(1) means "constant — same speed regardless of input size." O(n) means "linear — doubles when input doubles." O(n²) means "quadratic — quadruples when input doubles." It's the language engineers use to compare algorithms without running them.

The common complexity classes, ranked best to worst

Notation	Name	Example operation	1k items	1M items
O(1)	Constant	Hash map lookup, array index	1 op	1 op
O(log n)	Logarithmic	Binary search, B-tree lookup	10 ops	20 ops
O(n)	Linear	Loop through array	1k ops	1M ops
O(n log n)	Log-linear	Mergesort, quicksort, fast Fourier	10k ops	20M ops
O(n²)	Quadratic	Nested loop comparison	1M ops	1 trillion ops
O(n³)	Cubic	Naive matrix multiplication	1B ops	1 quintillion ops
O(2ⁿ)	Exponential	Naive recursion (Fibonacci)	infeasible	infeasible
O(n!)	Factorial	Permutations / brute-force traveling salesman	infeasible	infeasible

Code examples

O(1) — constant

function getFirst(arr) {
  return arr[0];  // always 1 step regardless of arr.length
}

O(n) — linear

function sum(arr) {
  let total = 0;
  for (const x of arr) total += x;  // n steps for n items
  return total;
}

O(log n) — logarithmic

function binarySearch(sorted, target) {
  let lo = 0, hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}
// Halves the search space each step → log₂(n) steps

O(n²) — quadratic (the trap)

function findDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) return arr[i];
    }
  }
}
// Nested loops over n items → ~n²/2 comparisons

Same job in O(n) using a Set:

function findDuplicate(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(x)) return x;
    seen.add(x);
  }
}

Why it matters in practice

For 100 items, even O(n²) is fast (10,000 operations = sub-millisecond). For 1 million items, O(n²) is 1 trillion operations — minutes to hours. Picking the right algorithm becomes critical at scale; for tiny inputs, simpler O(n²) code can be more readable and equally fast.

What Big O hides

• Constants: O(2n) and O(n) are both written O(n). In practice, an algorithm that does 100 ops per item can be slower than one that does 1 op per item.
• Best vs worst case: Big O is usually worst case. Quicksort is O(n²) worst case but O(n log n) average. Hash map lookup is O(1) average but O(n) worst case (collisions).
• Cache effects: O(n) iterating through a contiguous array is dramatically faster than the same Big O traversing a linked list because of CPU cache locality.
• Constant overhead: O(1) doesn't mean instant. A hash map lookup is "constant time" but takes longer than an array index.

Space complexity

Big O also describes memory usage. An algorithm that allocates a copy of an array uses O(n) extra space. One that sorts in place uses O(1) extra space (auxiliary). The same Big O notation, different metric.

Related tools

Performance issues in regex are usually catastrophic backtracking — O(2ⁿ) on adversarial input. Test patterns: regex tester. For data exploration to find slow query patterns, pretty-print API responses: JSON formatter.