Time & Space Complexity

Every algorithm consumes two resources: the work it performs and the memory it holds while performing it. Time complexity describes how the number of operations grows as the input grows. Space complexity describes how the amount of memory grows as the input grows. Both are written as functions of the input size, conventionally called n, and both are expressed with asymptotic notation such as O(n) or O(log n).

The word "grows" is the important one. Neither measure is interested in a single number — not milliseconds, not kilobytes. Both answer the same shaped question: if the input doubles, what happens? An O(n) algorithm does twice the work. An O(n²) algorithm does four times the work. An O(log n) algorithm does one extra step. That difference is the whole reason the subject exists, because it decides whether your program still works when the data gets big.

Timing code with a stopwatch is genuinely useful — it is called benchmarking, and you should do it before optimising anything. But it cannot replace complexity analysis, for four reasons:

• The number depends on the machine.
  • The same code times differently on a laptop, a phone and a server, so a measurement in seconds says as much about the hardware as it does about the algorithm.
• The number depends on the input you happened to pick.
  • Sorting an already-sorted array can be dramatically faster or slower than sorting a shuffled one, depending on the algorithm.
• The number tells you nothing about tomorrow's input.
  • Knowing that a function takes 40 ms on 1,000 records does not tell you whether 1,000,000 records will take 40 seconds or 11 hours. The growth rate does.
• You often need the answer before you write the code.
  • Complexity analysis lets you reject an approach on paper instead of discovering the problem after a week of implementation.

To count operations at all, you need to agree on what one operation is. Analysis uses a simplified machine called the RAM model, in which each of the following costs one unit of time:

• Arithmetic and comparison on fixed-size numbers: a + b, a < b, a % b.
• Assigning to a variable, reading a variable.
• Indexing an array: arr[i].
• Following a reference or pointer: node.next.
• Calling a function — the call itself, not the work inside it.

The model is a deliberate simplification — it ignores CPU caches, branch prediction and memory latency, all of which matter in real benchmarks. What it buys you is a count that is independent of any particular processor, which is exactly what makes complexity portable knowledge rather than a property of your laptop.

Take a function that sums an array. To find its time complexity, count how many times each line executes for an input of size n:

function sumArray(arr) {
  let total = 0;                     // 1 operation
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];                 // runs n times
  }
  return total;                      // 1 operation
}

Adding the column gives T(n) = 3n + 4. Now apply the two simplification rules: drop the lower-order term (the constant 4) and drop the constant factor (the 3). What remains is O(n) — the cost is proportional to the number of elements, which matches the intuition that you must look at every element to add it up.

The space analysis of the same function is shorter. It allocates exactly two variables, total and i, no matter whether the array holds ten elements or ten million. That is O(1) auxiliary space.

Two inputs of the same size can cost wildly different amounts, so a single number is often not enough. Linear search is the classic illustration — it stops as soon as it finds the target:

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;   // may exit on the first iteration
  }
  return -1;                           // or run all the way to the end
}

The average case assumes every position is equally likely, which gives n/2 comparisons — still O(n) after dropping the constant. In practice the worst case is quoted most often, because it is the only one that comes with a guarantee. The average case matters when an algorithm's worst case is rare and pathological, which is precisely the argument for using quick sort despite its O(n²) worst case.

Most analysis in practice comes down to recognising loop shapes. These patterns cover the large majority of code you will ever need to analyse:

Two rules generate every row in that table. Nested loops multiply, because the inner loop restarts for each outer iteration. Sequential loops add, and since the sum is dominated by its largest term, an O(n) loop followed by an O(n²) loop is simply O(n²).

A recursive function does not wear its cost on its sleeve, because the work is spread across a tree of calls. The standard technique is to write a recurrence relation — an equation that defines the cost of size n in terms of smaller sizes — and then solve it.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;             // O(1)
  const mid = Math.floor(arr.length / 2);
  const left  = mergeSort(arr.slice(0, mid));  // T(n/2)
  const right = mergeSort(arr.slice(mid));     // T(n/2)
  return merge(left, right);                   // O(n)
}

Reading that directly off the code gives T(n) = 2T(n/2) + O(n): two subproblems of half the size, plus a linear merge. Solving it yields O(n log n) — there are log₂n levels of recursion, and every level does a total of O(n) work merging.

Solving recurrences is a topic of its own, with three standard tools: the Master Theorem, the substitution method and the recursion tree method. Each has its own module in this series.

Space complexity is measured the same way as time — as growth, not as a byte count — but it is split into parts that are easy to confuse:

• Auxiliary space — the extra memory your algorithm allocates.
  • Temporary arrays, hash maps, the recursion call stack, and any buffers you create.
  • This is what people almost always mean when they quote a space complexity.
• Input space — the memory the input itself occupies.
  • Total space complexity = input space + auxiliary space, but the input is usually excluded because you had to store it either way.
• The call stack — the part everyone forgets.
  • Every pending recursive call holds its parameters and local variables in memory, so recursion depth is a real space cost.

Unless a problem says otherwise, "space complexity" means auxiliary space. An in-place sort that rearranges the array it was given is O(1) space, even though the array itself occupies n slots, because the algorithm added nothing of its own.

Recursion allocates memory even when your code contains no new, no array literal and no map. Each pending call keeps a stack frame alive, and the peak is set by the depth of the recursion, not by the total number of calls:

This is the difference between an iterative and a recursive solution that otherwise look equivalent. Iterative binary search is O(1) space; the recursive version is O(log n). For binary search that difference is negligible, but for a recursion that descends n levels deep it is the difference between running and crashing.

Time and space can very often be exchanged for one another. Spending memory to avoid recomputation is the single most productive optimisation in algorithm design:

• Memoization trades memory for repeated work.
  • Naive recursive Fibonacci is O(2ⁿ) time and O(n) space. Caching each result makes it O(n) time and O(n) space — an enormous win for a small, bounded cost.
• Hash maps trade memory for lookup speed.
  • Scanning an array for duplicates is O(n²) time and O(1) space. A hash set makes it O(n) time and O(n) space.
• Counting sort trades memory for a linear sort.
  • It sorts in O(n + k) time by allocating a bucket for every possible value — fast when the value range k is small, wasteful when it is huge.
• In-place algorithms trade speed or simplicity for memory.
  • Heap sort sorts in O(n log n) time with O(1) auxiliary space, but it is slower in practice than merge sort, which needs O(n) extra memory.

The trade-off is not automatically worth taking. Extra memory means extra allocation, worse cache behaviour and, past a point, no memory left at all. The judgement is always the same question: is the work I am saving larger than the cost of the memory I am spending?

Choosing a data structure is choosing a set of complexities. This table is the reason a hash map is not always better than an array, and why a linked list is not always better than a dynamic array:

Read it as a set of trade-offs rather than a ranking. Hash tables give the best average lookup but lose all ordering, and their worst case is linear. Balanced trees are slower per operation but keep the data sorted, which makes range queries possible. Arrays have the best constant factors of anything on the list, because contiguous memory is what CPU caches are built for.

Sorting is where complexity analysis pays off most visibly, because the algorithms differ in every column:

Insertion sort's O(n) best case on nearly-sorted data is why real library sorts fall back to it for small or almost-ordered subarrays. Quick sort is usually the fastest in practice despite its O(n²) worst case, because its constant factors are small and it needs no merge buffer. Counting sort escapes the O(n log n) lower bound entirely by not comparing elements at all — which it can only do because it assumes the keys are small integers.

A modern processor handles very roughly 10⁸ simple operations per second. Working backwards from that gives a practical table: given the largest input you must support, this is the complexity you need to aim for.

Used in reverse, the table is a strong hint. If a problem states that n can be up to 200,000, an O(n²) solution would need roughly 4 × 10¹⁰ operations and is hopeless — so the intended answer is almost certainly O(n log n) or better, and you can stop trying to make nested loops work.

1. Decide what n actually is.
   • The number of array elements, the number of nodes and edges, the length of the string, the number of digits — name it before you count anything.
2. Find the deepest, most-repeated block of work.
   • The complexity is almost always decided by the innermost statement of the deepest loop or the recursion.
3. Count how many times that block runs, in terms of n.
   • Multiply nested loops, add sequential ones.
4. Check whether every operation inside is really O(1).
   • Slicing a list, concatenating strings, or calling `in` on an array inside a loop quietly adds a factor of n.
5. Drop constants and lower-order terms.
   • 3n² + 10n + 50 becomes O(n²).
6. Repeat the whole process for memory.
   • Count the largest data structure alive at any one moment, and add the maximum recursion depth.

• Assuming a built-in function is free.
  • arr.includes(x), list.index(x), string concatenation in a loop and array.shift() are not O(1). A single innocent-looking call inside a loop is the most common cause of an accidental O(n²).
• Collapsing two different sizes into one.
  • Looping over n rows and m columns is O(n · m). Writing O(n²) is only correct when n and m are genuinely the same quantity.
• Forgetting the recursion stack in space analysis.
  • A recursive function that allocates nothing is still not O(1) space — a depth-n recursion holds n frames, which is exactly why deep recursion throws a "maximum call stack size exceeded" error.
• Confusing the worst case with Big-O.
  • They are separate axes. Big-O is an upper bound on growth; best/average/worst describes which input you are analysing. You can legitimately say an algorithm is O(1) in the best case.
• Ignoring constants entirely in real code.
  • Two O(n) passes over a billion items really is twice as slow as one. Asymptotics choose the approach; constants decide whether the implementation is good.
• Counting the output as auxiliary space when it is required.
  • If a problem asks you to return an array of n results, that array is output space, not overhead. State clearly which convention you are using.

• Complexity measures growth as a function of input size, not seconds or bytes.
• Time complexity counts operations; space complexity counts the memory alive at the peak, including the recursion stack.
• Nested loops multiply, sequential loops add, and only the dominant term survives.
• Best, average and worst case describe the input; O, Ω and Θ describe the bound. They are independent.
• Memory can usually be traded for speed — memoization, hashing and precomputed tables are all the same bargain.
• Let the input size pick your target complexity before you start writing code.