Complexity Analysis: The Hardware-Independent Ruler

Complexity analysis measures how an algorithm’s resource consumption grows as input size n grows — not how many milliseconds it runs. It answers the question “what happens to the cost when the input doubles?” with a growth rate that strips away hardware, compiler, and constant-factor noise, giving a language to compare algorithms without running them.

What the Notation Measures

Complexity analysis counts fundamental operations — comparisons, array accesses, arithmetic steps — as a function of n. The same algorithm in C and in Python has wildly different absolute runtimes but the same asymptotic class: the shape of the growth curve is what matters, not its height.

Time vs Space

• Time complexity — the count of fundamental operations as a function of n.
• Space complexity — peak memory used, including auxiliary structures, excluding the input itself (unless the algorithm copies it).

Recursive algorithms frequently trade the two: memoized dynamic programming turns exponential time into polynomial time by spending O(n) extra space on a table of subproblem answers.

Big-O, Big-Omega, Big-Theta

f(n) = Θ(g(n)) exactly when f(n) = O(g(n)) and f(n) = Ω(g(n)). Interview shorthand conflates them — “O(n)” usually means the tight worst case. Keep the three cases straight: worst case (what you typically analyze), best case (e.g. already-sorted input for quicksort), average case (expected cost over all inputs).

Common Growth Classes

The jump between classes is the real lesson: an O(n²) algorithm that handles 10⁴ inputs comfortably dies at 10⁶ (10¹² steps), while O(n log n) survives the same jump in milliseconds.

Deriving Complexity from Loops

Three rules cover most iterative algorithms:

• Sum rule (sequential blocks): the total cost of consecutive blocks is the sum of their costs — keep the dominant term. O(f) then O(g) → O(f + g) → O(max(f, g)).
• Product rule (nested loops): a loop of n iterations whose body costs O(g) is O(n·g). Two nested loops over n are O(n²).
• Logarithms: each time the input (or search space) is halved — binary search, balanced-BST descent, divide-and-conquer depth — the iteration count gains a log factor.

// O(n) — a single pass
for (let i = 0; i < n; i++) work();

// O(n²) — n iterations, each doing O(n) work
for (let i = 0; i < n; i++)
  for (let j = 0; j < n; j++) work();

// O(n log n) — halving bound (log n iterations) × O(n) inner work
for (let i = n; i > 1; i = Math.floor(i / 2))
  for (let j = 0; j < n; j++) work();

// O(log n) — halving with constant work per step
while (n > 1) n = Math.floor(n / 2);

Amortized Analysis

Amortized analysis charges an average cost across a sequence of operations, giving a realistic per-operation bound when expensive steps are rare. The canonical case is the dynamic array (JavaScript’s push): most appends are O(1), but when the backing array is full, resizing copies all n elements — an O(n) operation. Because resizing happens only once per ~n cheap appends, the amortized cost is O(1) per append even though any single append can be O(n). Amortized is an average over the sequence, not over random inputs.

When Big-O Misleads

Asymptotic class is the ceiling, not the number:

• Constants matter at scale: an O(n) algorithm doing 100 units per element loses to an O(n log n) algorithm doing 1 unit per element until n is enormous.
• Cache locality: an array-backed O(n) scan streams memory; a linked-list O(n) traversal jumps across cache lines and can be 10–100× slower at the same class.
• Small inputs: for n < 20, a naive O(2ⁿ) brute force can beat a clever O(n log n) algorithm — the clever one’s constants dominate.
• Real inputs are finite: the asymptote is far away; when performance matters, measure.

Worked Example

Check an array of n integers for duplicates, two ways.

Brute force — for each element, scan the rest:

for (let i = 0; i < n; i++)
  for (let j = i + 1; j < n; j++)
    if (a[i] === a[j]) return true; // O(n²) worst case

Hash set — one pass, O(n) space:

const seen = new Set<number>();
for (const x of a) {
  if (seen.has(x)) return true; // O(1) average
  seen.add(x);
}
return false; // O(n) total

The same problem in two classes: O(n²) time with O(1) extra space versus O(n) time with O(n) space. For n = 1,000,000 the first is ~10¹² comparisons (minutes); the second is ~1M hashes (milliseconds). This is the exact trade-off that shows up in system design: time can be bought with memory, but never with asymptotic luck.

Practice Trajectory

1. Take a function you wrote and label every loop with its class; combine them with the sum and product rules.
2. Convert an O(n²) double loop into an O(n) hash-set solution and benchmark both.
3. Derive by hand — then confirm by benchmark — the class of binary search, merge sort, and naive Fibonacci.
4. Explain why while (n > 1) n /= 2 is O(log n) and why nesting a full O(n) pass inside it makes the total O(n log n).
5. Rewrite a recursive function iteratively and compare the space complexity of both versions.

When It’s the Right Tool