Complexity Analysis

Complexity analysis is not about being mathematically precise. It is about having a shared vocabulary to say "this will be fast enough" or "this will blow up" before writing any code. Every interview answer starts with "the time complexity is..." -- you need to be fluent.

Big-O, Big-Theta, Big-Omega

• Big-O (O) -- Upper bound. "This algorithm is at most this slow." This is what interviews care about.
• Big-Omega (Omega) -- Lower bound. "This algorithm is at least this fast."
• Big-Theta (Theta) -- Tight bound. "This algorithm is exactly this fast." When someone says "O(n)" in conversation, they usually mean Theta(n).

In practice, you almost always use Big-O. When an interviewer asks for time complexity, give the worst-case Big-O unless they specifically ask for best-case or average-case.

The Common Complexities

From fastest to slowest:

The practical cutoffs for competitive programming and interviews (assuming ~10^8 operations per second):

• n <= 20: O(2^n) or O(n!) is fine
• n <= 1,000: O(n^2) is fine
• n <= 100,000: O(n log n) is fine
• n <= 10,000,000: O(n) is required
• n > 10,000,000: O(log n) or O(1) is required

Analyzing Loops

Single Loop

// O(n)
function sum(arr: number[]): number {
  let total = 0;
  for (const num of arr) {  // runs n times
    total += num;            // O(1) work per iteration
  }
  return total;
}

Nested Loops

// O(n^2) -- both loops depend on n
function allPairs(arr: number[]): void {
  for (let i = 0; i < arr.length; i++) {       // n times
    for (let j = i + 1; j < arr.length; j++) {  // up to n times
      console.log(arr[i], arr[j]);
    }
  }
}

// O(n * m) -- loops depend on different inputs
function crossProduct(a: number[], b: number[]): void {
  for (const x of a) {   // n times
    for (const y of b) {  // m times
      console.log(x, y);
    }
  }
}

Loops with Multiplicative Steps

// O(log n) -- i doubles each time
function logLoop(n: number): void {
  let i = 1;
  while (i < n) {
    i *= 2;  // reaches n in log2(n) steps
  }
}

Analyzing Recursion

Use the recurrence relation approach.

Linear Recursion

// T(n) = T(n-1) + O(1) => O(n)
function factorial(n: number): number {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

Binary Recursion (Divide and Conquer)

// T(n) = 2T(n/2) + O(n) => O(n log n)  (merge sort pattern)
// T(n) = 2T(n/2) + O(1) => O(n)          (binary tree traversal)
// T(n) = T(n/2) + O(1)  => O(log n)      (binary search)

Exponential Recursion

// T(n) = 2T(n-1) + O(1) => O(2^n)
function fibonacci(n: number): number {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

The Master Theorem (simplified): For T(n) = aT(n/b) + O(n^d):

• If d > log_b(a): O(n^d)
• If d = log_b(a): O(n^d * log n)
• If d < log_b(a): O(n^(log_b(a)))

You rarely need to apply this formally in interviews, but knowing it exists helps you verify your intuition.

Space Complexity

Space complexity counts the additional memory your algorithm uses, not counting the input.

// Time: O(n), Space: O(1) -- only uses a few variables
function findMax(arr: number[]): number {
  let max = -Infinity;
  for (const num of arr) {
    if (num > max) max = num;
  }
  return max;
}

// Time: O(n), Space: O(n) -- creates a new array
function doubleAll(arr: number[]): number[] {
  return arr.map(x => x * 2);
}

// Time: O(n), Space: O(n) -- call stack counts
function sumRecursive(arr: number[], i = 0): number {
  if (i >= arr.length) return 0;
  return arr[i] + sumRecursive(arr, i + 1);  // stack depth = n
}

Recursive call stack counts as space. This catches people off guard. A recursive DFS on a tree uses O(h) space where h is the tree height. On a balanced tree that is O(log n); on a skewed tree it is O(n).

Amortized Analysis

Some operations are expensive occasionally but cheap most of the time. Amortized analysis averages the cost over a sequence of operations.

Classic example: dynamic array (ArrayList, JavaScript array push)

// Individual push: usually O(1), but O(n) when resizing
// Amortized over n pushes: O(1) per push
//
// Why: resizing doubles capacity. After n pushes, total copying work is:
// 1 + 2 + 4 + 8 + ... + n = 2n - 1 = O(n)
// Spread over n operations: O(n) / n = O(1) per operation

Other amortized O(1) examples:

• Hash map insertions (rehashing is rare)
• Splay tree operations (individual ops can be O(n), but any sequence of m operations is O(m log n))

Common Operation Complexities

Sorting Algorithm Complexities

Tips for Interviews

1. Always state complexity first. Before coding, tell the interviewer: "This approach is O(n log n) time, O(n) space." It shows you think before you type.
2. When in doubt, count the work. How many times does each element get touched? If every element gets touched once, it is O(n). If every element gets compared to every other, it is O(n^2).
3. Drop constants and lower-order terms. O(2n) is O(n). O(n^2 + n) is O(n^2). O(n/2) is O(n).
4. Log bases do not matter for Big-O. O(log2 n) = O(log10 n) = O(ln n) because log bases differ by a constant factor.
5. Space-time tradeoffs are expected. "I can do this in O(n^2) time with O(1) space, or O(n) time with O(n) space" is exactly the kind of analysis interviewers want.