How is an algorithm's memory usage measured?

AlgorithmsJunior~4 min read

Short answer

An algorithm's memory usage is measured as space complexity S(n) - a function of the input size n. It is usually stated as an asymptotic O-notation estimate for the peak amount of auxiliary memory the algorithm uses at once: variables, temporary data structures, and the recursion stack. When needed, total memory (input + output + auxiliary) is distinguished from auxiliary memory, and the case the estimate is for (worst, average, amortized) is clarified.

Detailed answer

What exactly is measured

Total memory: S_total(n) = S_input(n) + S_output(n) + S_aux(n).
Auxiliary memory: everything the algorithm allocates beyond storing the input and the result. Interviews usually ask about this one specifically.
Peak value: the maximum simultaneous memory usage over the whole run, not the total allocated/freed.
Case: worst-case, average-case, or amortized. Do not forget to clarify this in your answer.

Model and units of measurement

The RAM/word-RAM model is usually used: memory is counted in machine words (or bytes), then simplified to a function of n, and the asymptotics is taken.

Scalar variables: O(1).
An array of length k: O(k). An n×m matrix: O(n·m).
A hash table/dictionary with k elements: O(k).
A recursive call of depth h: O(h) extra memory for the stack.

How to estimate it in practice (a step-by-step approach)

Decide what to count: total or auxiliary memory; peak or total allocated.
Split the algorithm into phases and list the data structures that are simultaneously alive.
Account for the recursion stack or an internal stack/queue during traversals.
Add up the sizes (in words/bytes) and express them as S(n); simplify to O(·), Θ(·), or Ω(·).
Clarify the case (worst/average/amortized) and dependencies on additional parameters (k - number of unique items, V/E - graph size, etc.).
If needed, give a precise byte estimate for a specific implementation (for example, 4 bytes for a 32-bit integer).

Typical components of memory usage

Storing the input data (often not included in auxiliary).
Memory for the output (often counted separately; for example, returning a new array of length k is O(k)).
Temporary structures: arrays, hash tables, queues/stacks, buffers.
The recursion stack or the depth of an iterative stack during traversals.
Structure overhead (object headers, pointers) - accounted for in precise counts but dropped in the asymptotics.

Short example estimates

Finding the maximum in an array with a single pass: O(1) auxiliary.
Counting frequencies with a Map over n elements: O(k), where k is the number of unique values (k ≤ n).
BFS on a graph: a queue O(V), a visited array O(V) → auxiliary O(V).
Merge sort: O(n) extra memory; quicksort: O(log n) stack on average, O(n) in the worst case.
DP with an n×m table: O(nm), but sometimes it can be optimized to O(min(n, m)) memory by keeping only the needed row/column.

Code examples

Two approaches to the two-sum problem show the difference in auxiliary memory.

// Example 1: finding a pair that sums to target - different memory profiles
// Variant A: a hash table - O(n) extra memory
function twoSumHash(nums, target) {
  const map = new Map(); // up to n entries ⇒ O(n)
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (map.has(need)) return [map.get(need), i];
    map.set(nums[i], i);
  }
  return null;
}

// Variant B: two pointers after sorting - O(1) extra memory (if the sort is in-place)
// Important caveats:
// - If the sort is quicksort (in-place), the recursion stack is ≈ O(log n) on average.
// - If the sort is a stable merge sort, extra memory can be O(n).
function twoSumTwoPointers(nums, target) {
  nums.sort((a, b) => a - b); // potentially O(1) auxiliary + O(log n) stack, depends on the implementation
  let l = 0, r = nums.length - 1; // a few scalars ⇒ O(1)
  while (l < r) {
    const sum = nums[l] + nums[r]; // O(1)
    if (sum === target) return [nums[l], nums[r]]; // return the result (output memory)
    if (sum < target) l++; else r--;
  }
  return null;
}

Recursion vs. iteration: both are O(h), where h is the maximum depth.

// Example 2: tree traversal - memory due to depth
// Recursive DFS: O(h) due to the call stack
function dfsRec(node) {
  if (!node) return;          // O(1)
  // ... process node
  dfsRec(node.left);          // depth grows ⇒ memory O(h)
  dfsRec(node.right);
}

// Iterative DFS with its own stack: also O(h), but we control the stack
function dfsIter(root) {
  if (!root) return;
  const stack = [root]; // up to h elements at the peak ⇒ O(h)
  while (stack.length) {
    const node = stack.pop(); // O(1)
    // ... process node
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
}

Frequent mistakes

Counting the total allocated memory instead of the peak simultaneous usage.
Forgetting about the recursion stack (even when no data structures are explicitly created).
Not clarifying whether the input and output are included in the estimate (auxiliary vs total).
Confusing in-place operations with ones that create copies (for example, methods that return a new array).
Ignoring parameters other than n (for example, k - the number of unique values, the range of values, V and E in graphs).
Giving an average-case estimate where the worst-case behavior matters.

Summary

To measure an algorithm's memory usage, list the objects that are alive at the same time, add up their total size, express it as a function of the input parameters, and then give an asymptotic estimate (usually for peak auxiliary usage). Do not forget the recursion stack, clarify whether the input and output are included, and state which case the estimate is for.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.