Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 225 ยท Analyzing Algorithms

Space Complexity

Learn how to measure the memory an algorithm uses. Auxiliary space vs input space, recursion stack cost, in-place algorithms and time-space trade-offs in Python.

Time is only half of the cost of an algorithm. Every program also needs memory: for the variables it creates, the lists it builds, and the calls waiting on the call stack. An algorithm that runs fast but needs ten gigabytes of RAM is useless on a phone, and one that needs memory proportional to a billion-item input may not run at all. Space complexity describes how the memory an algorithm uses grows with the size of its input, using the same Big O language you already know.

This lesson shows what to count, what to ignore, how recursion quietly uses memory, and how to trade space for time (and the other way round).

What counts as space?

Space complexity splits into two parts:

  • Input space: the memory that holds the input itself. A list of n numbers takes O(n) space no matter what you do with it.
  • Auxiliary space: the extra memory your algorithm allocates while it works: new lists, dictionaries, sets, strings, and the call stack.

When people say "this algorithm uses O(1) space", they almost always mean auxiliary space: it needs only a few extra variables beyond the input. A sort that works on the list you give it uses O(1) auxiliary space; a sort that builds a second list uses O(n).

TEXT
input list  [ 7 | 2 | 9 | 4 ]           <- input space, always O(n)

in place:    a few variables  i, j, tmp   <- auxiliary O(1)
with copy:   [ 4 | 9 | 2 | 7 ]  new list  <- auxiliary O(n)

The state of the whole program (the input plus everything extra) is called total space. Textbooks and interviewers differ on which one they mean, so say "auxiliary" when you want to be precise.

Counting extra memory

Look for anything whose size depends on n: a list that grows with a loop, a dictionary filled from the input, a string built piece by piece. A fixed number of integers or booleans is O(1).

Python Two ways to reverse a list

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

reverse_copy leaves the original alone and costs O(n) extra space. reverse_in_place changes the list it was given and costs O(1). Neither is better in general: if the caller still needs the original, copying is the safe choice. Knowing the cost lets you choose on purpose.

An in-place algorithm transforms its input using O(1) (or sometimes O(log n)) extra space. The price is that the input is changed, which can surprise callers. Python's list.sort() works in place, while sorted(lst) returns a new list.

Recursion uses space too

Every function call gets a stack frame: a small block of memory that holds the arguments, local variables and the place to return to. In recursion, the frames pile up until the base case is reached. If a function calls itself d levels deep, it uses O(d) stack space, even if it creates no lists at all.

TEXT
total(4)
 โ””โ”€ total(3)
     โ””โ”€ total(2)
         โ””โ”€ total(1)
             โ””โ”€ total(0)      <- deepest: 5 frames alive at once
Python Measuring recursion depth

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

total_recursive(n) needs n + 1 frames at the deepest point, so it uses O(n) space, while the loop version uses O(1). The recursive binary search halves the range each call, so even a million items need only about twenty frames: O(log n) space.

Python limits the depth to protect itself from endless recursion (by default about a thousand frames). Going past it raises RecursionError:

Python Hitting the recursion limit (caught)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This is why a problem that is "obviously recursive" still deserves a second look when n can be large. The tools in recursion include converting to a loop with your own explicit stack, which moves the memory from the call stack to a list.

Tail-call elimination does not exist in Python. Even a function whose last action is the recursive call keeps all its frames. For deep linear recursion, write a loop.

Typical space costs

Algorithm or structure Auxiliary space Why
Linear scan, sum, max O(1) a couple of variables
Reverse or swap in place O(1) swaps only
Building a result list from input O(n) one output item per input item
Recursion of depth d O(d) one frame per level
Binary search (recursive / loop) O(log n) / O(1) depth log n, or just lo and hi
Merge sort O(n) merging needs a temporary list
Quick sort (in place) O(log n) average recursion stack only
Hash set of n items O(n) stores every item
Grid or matrix of n ร— m cells O(n ร— m) one cell each
Memoized recursion with k subproblems O(k) the cache, plus the stack

Notice that "does it create a collection?" and "how deep does it recurse?" answer most questions.

Trading time for space

You often can buy speed with memory, or save memory by doing more work. This is called a time-space trade-off, and it appears in almost every chapter. Take the two-sum problem: do two numbers in a list add up to a target?

Python Two-sum: brute force vs a set

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The brute force examines every pair (499,500 of them for 1000 numbers) but remembers nothing. The set version does 1000 lookups but stores up to 1000 numbers. Which is right depends on the situation: if the list has a billion items and memory is tight, the O(1)-space idea might win, although a sorted list lets you reach O(n) time and O(1) space with two pointers.

Memoization is the classic example of spending space to save time. Plain recursive Fibonacci recomputes the same values over and over; caching them makes each value cost one call.

Python Memoization: space for speed

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cache grows to n โˆ’ 1 entries, which is O(n) space, and the number of calls drops from exponential to linear. You will see this trade in detail in memoization vs tabulation. Sometimes you can even have both: the tabulated Fibonacci needs only the last two values, so it takes O(n) time and O(1) space. Dynamic programming often lets you keep just a few rows of a table instead of all of them (see one-dimensional DP).

Common mistakes

  • Forgetting the output. Whether the answer list counts as space depends on the convention. Be consistent and say which one you use.
  • Hiding copies. lst[:], lst[1:], sorted(lst), list(x), and s + t all allocate new memory. A recursive function that slices its input on every call can use O(nยฒ) space in total.
  • Ignoring the call stack. "No extra data structure" is not the same as O(1) space if the function recurses n deep.
  • Counting constants as growth. Three variables or a 26-letter alphabet table are O(1), even though they are not zero.
  • Assuming strings are free. Strings are immutable in Python, so each concatenation in a loop makes a new one.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does auxiliary space measure?

    Auxiliary space counts the additional memory used while running: new collections, variables that scale with n, and the call stack. The input itself is counted separately.
  2. 2. A recursive function calls itself n times in a chain, once per level, and builds no lists. What is its space complexity?

    Each pending call keeps a stack frame, so n nested calls hold n frames at once: O(n) space.
  3. 3. Which of these is an in-place algorithm?

    Two-pointer reversal only needs a few index variables, and it changes the list itself, so it uses O(1) extra space.
  4. 4. Memoizing recursive Fibonacci with a dictionary changes the cost how?

    The dictionary stores n subresults (O(n) space), and each is computed only once, so the number of calls drops from exponential to linear.
  5. 5. Why can a deep recursion raise RecursionError even when the algorithm is correct?

    The call stack is finite. Python stops runaway recursion by raising RecursionError at its depth limit (about 1000 by default).

Summary

  • Space complexity measures how memory grows with the input; auxiliary space excludes the input itself.
  • Look for collections whose size scales with n, copies made by slicing or concatenation, and recursion depth.
  • Each recursive call keeps a stack frame, so depth d costs O(d) space; Python caps the depth.
  • In-place algorithms use O(1) extra space but change their input.
  • Time and space often trade against each other: sets and memoization spend memory to save time; two-pointer and loop versions save memory.
  • State clearly whether your answer is auxiliary or total space.

Next: Best, Worst and Average Case