Level 1 · 25 min

Big-O Notation: Reading the Time Curve

Big-O is the language engineers use to describe how an algorithm scales. It is not about wall-clock time on your laptop — it is about the asymptotic shape of the cost function as input size n grows. CLRS introduces it in chapter 3 as a mathematical tool to compare algorithms independently of constants, hardware, and compiler optimizations.

The Three Bounds: O, Theta, Omega

CLRS defines three asymptotic notations: O(g(n)) is the upper bound (worst case bounded by c·g(n) for sufficiently large n), Omega(g(n)) is the lower bound, and Theta(g(n)) is the tight bound when both apply. Most interview answers conflate O with Theta — saying ''insertion sort is O(n^2)'' when they mean Theta(n^2). The distinction matters: linear search is O(n) and Omega(1) (best case finds the target immediately), so it has no single Theta bound across all inputs. Be precise: state whether you are giving worst-case, best-case, or amortized analysis.

Reading the Hierarchy

Memorize the dominance order: O(1) '<' O(log n) '<' O(sqrt n) '<' O(n) '<' O(n log n) '<' O(n^2) '<' O(n^3) '<' O(2^n) '<' O(n!). At n=1000, O(n^2) is one million ops (microseconds); O(2^n) is 10^301 ops (heat death of universe). Cracking the Coding Interview chapter VI hammers this: any nested loop over the same input is O(n^2), and a recursive call that branches into two subproblems each on n/2 input is O(n log n) by the Master Theorem. Drop constants and lower-order terms: O(3n^2 + 100n + 5) collapses to O(n^2) because for large n the n^2 term dominates.

Amortized Analysis and Common Traps

Amortized analysis (CLRS chapter 17) explains why ArrayList.add() is O(1) average despite occasional O(n) resizes — the cost of doublings is spread across n operations using the aggregate or accounting method. Common traps: (1) hidden loops in built-ins — Python ''in list'' is O(n), Java String.contains() is O(n·m); (2) string concatenation in a loop is O(n^2) because each + builds a new string; (3) sum of arithmetic series 1+2+...+n = n(n+1)/2 = O(n^2), so a loop ''for i: for j in range(i)'' is O(n^2) not O(n). Always count the work per iteration and the iteration count separately.

Key Takeaways

Big-O drops constants and low-order terms — focus on the dominating term as n grows.
Specify which case you mean: worst, best, average, or amortized. Conflating O with Theta is the #1 interview mistake.
Nested loops over the same input give O(n^2). Halving each call gives O(log n). Doubling work each step gives O(2^n).

Code example

// Java — three implementations of "find duplicate", increasing in efficiency

// O(n^2) — nested scan, the naive approach
boolean hasDupNaive(int[] a) {
  for (int i = 0; i < a.length; i++)
    for (int j = i + 1; j < a.length; j++)
      if (a[i] == a[j]) return true;
  return false;
}

// O(n log n) — sort then scan adjacent pairs
boolean hasDupSorted(int[] a) {
  int[] copy = a.clone();
  Arrays.sort(copy);                     // n log n
  for (int i = 1; i < copy.length; i++) // n
    if (copy[i] == copy[i-1]) return true;
  return false;
}

// O(n) average — hash set probe; O(n) worst case if all keys collide
boolean hasDupHash(int[] a) {
  Set<Integer> seen = new HashSet<'>(a.length * 2);
  for (int x : a) if (!seen.add(x)) return true;
  return false;
}