Complexity Analysis

What Is Big O?

Big O notation describes how an algorithm's resource usage grows as the input size increases. It strips away constants and low-order terms to focus on the dominant factor. The question it answers: "As n gets very large, what happens to the running time (or memory)?"

There are three related notations. In practice, interviews almost always mean Big O (upper bound):

• O (Big O) — upper bound. "At most this fast." The one you will use 99% of the time.
• Ω (Omega) — lower bound. "At least this slow." Useful for proving optimality.
• Θ (Theta) — tight bound. "Exactly this growth rate." Means both O and Ω match.

Common Complexities

Every algorithm falls into one of these growth classes. Memorize this hierarchy — you will reference it in every interview. Listed from fastest to slowest:

To put these in perspective, here is how many operations each complexity produces for n = 1,000:

Deriving Time Complexity

Follow this systematic method to derive the time complexity of any algorithm. These four rules cover the vast majority of interview problems.

Let's apply these rules to a concrete example — the two-pointer approach for finding a pair that sums to a target in a sorted array:

function twoSum(nums, target) {
  let left = 0, right = nums.length - 1;  // O(1)

  while (left < right) {                   // Runs at most n times
    const sum = nums[left] + nums[right];  // O(1) per iteration
    if (sum === target) return [left, right];
    if (sum < target) left++;
    else right--;
  }
  return [];
}

Deriving Space Complexity

Space complexity measures how much extra memory grows with input size. The input itself usually does not count — only the auxiliary memory your algorithm allocates.

Ask yourself: "What new data structures or stack frames grow as n increases?"

• Hash maps, sets, arrays — if you build one proportional to input size, that is O(n) space.
• Recursion stack frames — each recursive call adds a frame. DFS on a tree uses O(h) space where h is the tree height.
• In-place mutation — modifying the input array uses O(1) extra space.
• Copies and slices — arr.slice() creates a new array of up to O(n) size.

Amortized & Average Case

Amortized analysis looks at the average cost per operation over a sequence of operations, even if individual operations occasionally spike. Average case looks at the expected cost over all possible inputs.

Push 1  → capacity 1  (copy 0 elements)
Push 2  → capacity 2  (copy 1 element)
Push 3  → capacity 4  (copy 2 elements)
Push 5  → capacity 8  (copy 4 elements)
Push 9  → capacity 16 (copy 8 elements)
...
Total copies for n pushes: 1+2+4+8+...+n = 2n - 1

Other amortized O(1) operations you should know:

• Hash map get/set — O(1) amortized. Worst case O(n) if every key collides, but this almost never happens with a good hash function.
• Monotonic stack — each element is pushed and popped at most once across the entire loop. O(n) total for n elements = O(1) amortized per element.
• Union-Find with path compression + union by rank — O(α(n)) amortized per operation, where α is the inverse Ackermann function (effectively constant).

Recurrence Relations

Recursive algorithms produce recurrence relations of the form T(n) = aT(n/b) + O(n^d), where a is the number of subproblems, n/b is each subproblem's size, and O(n^d) is the work done outside the recursive calls.

Here are the most common recurrences you will encounter in interviews:

Pattern Complexity Reference

A complete reference table for all 27 algorithm patterns. The Brute Force column shows the naive approach; Optimal shows what the pattern achieves.

Shortcuts & Traps

These shortcuts let you derive complexity in seconds during an interview. Memorize the rules, then watch out for the traps that catch even experienced candidates.

Shortcuts

Common Traps

Walkthrough: Deriving Complexity

Let's walk through a complete complexity derivation for a classic problem: finding duplicates in an array. We will analyze three approaches with increasing sophistication, showing the time-space tradeoff in action.

function hasDuplicate(nums) {
  for (let i = 0; i < nums.length; i++) {       // n iterations
    for (let j = i + 1; j < nums.length; j++) { // up to n-1 iterations
      if (nums[i] === nums[j]) return true;     // O(1) comparison
    }
  }
  return false;
}

function hasDuplicate(nums) {
  nums.sort((a, b) => a - b);                   // O(n log n)
  for (let i = 1; i < nums.length; i++) {       // O(n) scan
    if (nums[i] === nums[i - 1]) return true;   // O(1) comparison
  }
  return false;
}

function hasDuplicate(nums) {
  const seen = new Set();                        // O(n) space worst case
  for (const num of nums) {                      // O(n) iterations
    if (seen.has(num)) return true;              // O(1) amortized lookup
    seen.add(num);                               // O(1) amortized insert
  }
  return false;
}

Key Takeaways

Keep these five rules at the front of your mind during every interview. They will make complexity analysis feel automatic.