Time and space complexity

Overview

Time complexity measures how the number of operations grows with input size. Space complexity measures how much extra memory the algorithm needs beyond its input: variables, new arrays, hash maps, and the recursion call stack.

Analyzing both precisely is what separates a correct solution from an accepted one. This guide covers the practical techniques: counting loops, analyzing recursion with recursion trees and the Master Theorem, amortized analysis, and measuring stack space.

When to use it

• Before coding: to confirm the planned approach fits the constraints.
• After coding: to state the complexity of your solution in an interview.
• When a solution gets Time Limit Exceeded or Memory Limit Exceeded.
• When choosing between recursion and iteration, or between two data structures.

Problem patterns it solves

Where it is used in real software

Key terms

Auxiliary space

Extra memory used by the algorithm, excluding the input. This is what 'space complexity' usually means in interviews.

Call stack space

Each active recursive call keeps a frame in memory; recursion depth d costs O(d) space.

Recurrence relation

An equation such as T(n) = 2T(n/2) + n describing the cost of a recursive algorithm.

Master Theorem

A shortcut to solve T(n) = aT(n/b) + O(n^d) by comparing a with b^d.

Amortized O(1)

Occasional expensive operations are spread over many cheap ones so the average stays constant.

Analysis techniques

1. 1
   Iterative code: count iterations

   Multiply the iterations of nested loops. If the inner loop depends on the outer one (j from i to n), sum the series: 1 + 2 + ... + n = n(n + 1)/2 = O(n^2).

2. 2
   Logarithmic loops

   If a variable is multiplied or divided by a constant each step (i *= 2, n /= 2), the loop runs O(log n) times.

3. 3
   Recursion: draw the recursion tree

   Total work = work per call x number of calls. Fibonacci makes about 2^n calls with O(1) work each, so it is O(2^n).

4. 4
   Recursion: apply the Master Theorem

   For T(n) = aT(n/b) + O(n^d): if a < b^d then O(n^d); if a = b^d then O(n^d log n); if a > b^d then O(n^(log_b a)).

5. 5
   Amortized analysis

   Count total work over the whole run. In a monotonic stack, each element is pushed once and popped at most once, so the total is O(n) despite the inner while loop.

6. 6
   Space: find the peak memory

   Add the sizes of new data structures and the maximum recursion depth. Output arrays are usually excluded unless the question says otherwise.

Applying the Master Theorem

T(n) = a * T(n / b) + O(n^d)

Compare the number of subproblems (a) with how fast the combine work grows (b^d). The larger side dominates; if they tie, you pay the combine cost at each of log n levels.

Implementation

1// Time O(n^2), Space O(1): inner loop runs n-1, n-2, ... 1 times2function countPairs(arr) {3  let count = 0;4  for (let i = 0; i < arr.length; i++) {5    for (let j = i + 1; j < arr.length; j++) count++;6  }7  return count; // n(n-1)/28}9 10// Time O(n), not O(n^2): each index is pushed and popped at most once11function dailyTemperatures(temps) {12  const answer = new Array(temps.length).fill(0);13  const stack = [];14  for (let i = 0; i < temps.length; i++) {15    while (stack.length && temps[i] > temps[stack.at(-1)]) {16      const j = stack.pop();17      answer[j] = i - j;18    }19    stack.push(i);20  }21  return answer;22}23 24// Time O(n), Space O(n) because of the call stack25function sumRecursive(arr, i = 0) {26  if (i === arr.length) return 0;27  return arr[i] + sumRecursive(arr, i + 1);28}29 30// Time O(log n), Space O(log n): fast exponentiation31function power(x, n) {32  if (n === 0) return 1;33  const half = power(x, Math.floor(n / 2));34  return n % 2 === 0 ? half * half : half * half * x;35}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Calling a nested while loop O(n^2) automatically.

  Fix: Check how far the inner pointer moves in total. If it never resets, the total is O(n).

• Forgetting recursion stack space.

  Fix: A recursive DFS on a skewed tree or long list uses O(n) stack even with no extra arrays.

• Counting the output as auxiliary space without saying so.

  Fix: State your convention: 'O(1) extra space, excluding the output array'.

• Assuming memoized recursion has O(1) space.

  Fix: The memo table has one entry per state, and recursion depth still applies.

Interview questions

Practice problems