Space Complexity

Imagine two Class 8 students, Aditi and Rohan, are each asked to write a program that reverses a list of cricket scores from an India–Australia ODI series. Both programs are correct. Both run in a flash — well under a millisecond for a list of 40 scores. But now imagine the list grows to 4,00,000 scores (say, ball-by-ball data collected across an entire IPL season), and both programs are run on a budget smartphone with only 2 GB of RAM shared across a dozen open apps. Aditi's program still finishes without trouble. Rohan's crashes with an "out of memory" error before it even produces an answer. Both programs did the exact same job at the exact same speed on small inputs — so what changed at large inputs? Not time. Memory. The two programs used very different amounts of extra memory as the input grew, and that hidden cost — how the memory a program needs grows as its input grows — is called space complexity. It matters exactly as much as the running time (time complexity) you may already have studied, and for many real programs — apps on cheap phones, programs processing railway or exam data for the whole country — it matters more.

Two Ways to Reverse a List: Same Result, Different Memory Bills

Let's see exactly what Aditi and Rohan might have written. Suppose arr is a list of numbers, and the goal is to reverse it.

def reverse_in_place(arr):
    left = 0
    right = len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

def reverse_new_array(arr):
    result = []
    for i in range(len(arr) - 1, -1, -1):
        result.append(arr[i])
    return result

Trace reverse_in_place on arr = [1, 2, 3, 4, 5]. Start with left = 0, right = 4. Since 0 < 4, swap positions 0 and 4: the list becomes [5, 2, 3, 4, 1]. Now left = 1, right = 3; since 1 < 3, swap: [5, 4, 3, 2, 1]. Now left = 2, right = 2; the loop condition left < right is false, so it stops. The result is [5, 4, 3, 2, 1] — correctly reversed, and it was done by rearranging the same list in memory using two pointer variables.

reverse_new_array gets the same answer a completely different way: it builds a brand-new empty list, then walks backward through the original array (i starting at index 4, down to index 0), copying each element into result. For [1, 2, 3, 4, 5], it appends 5, then 4, then 3, then 2, then 1, giving [5, 4, 3, 2, 1] — the same correct answer, but by creating a second list that is exactly as large as the first.

Now count the extra memory each function needs, beyond the input list it was given. reverse_in_place uses exactly three small variables — left, right, and the temporary space Python uses internally to perform the swap — no matter whether arr has 5 elements or 5 crore elements. reverse_new_array, on the other hand, builds a second list whose size grows in exact lockstep with the input: reverse a list of 40 items, and you need room for 40 more items; reverse a list of 4,00,000 items, and you need room for 4,00,000 more. This is the core idea of space complexity: not "how much memory does the program use in total," but "how does the extra memory the program needs change as the input size, which we call n, grows?" We write this using a shorthand called Big-O notation. reverse_in_place needs a constant, unchanging amount of extra memory no matter how big n gets — we say it runs in O(1) space ("order 1," meaning constant). reverse_new_array needs extra memory that grows directly proportional to n — we say it runs in O(n) space ("order n," meaning linear).

Defining Space Complexity: the Fixed Part and the Variable Part

Formally, computer scientists split the total memory a program uses into two parts:

• Fixed part — memory whose size does not depend on the input at all: the compiled instructions of the program itself, simple constants, and a handful of individual variables like left, right, or a loop counter.
• Variable part — memory whose size depends directly on the input: arrays, lists, dictionaries, or recursive function calls (more on that shortly) that are created while the program runs, whose sizes scale with n.

If c stands for the fixed part (a constant number of bytes) and S(n) stands for the variable part as a function of input size n, then the total space used by a program is c + S(n). Because c never changes, when we describe an algorithm's space complexity we almost always focus on S(n) — how the variable part scales. This is exactly parallel to how, when studying time complexity, we ignore constant setup time and focus on how the number of operations grows with n.

One frequent misunderstanding is worth naming directly: space complexity is not about how many lines of code a program has, or how large the source file is on disk. A ten-line program that builds a huge list has far worse space complexity than a two-hundred-line program that only ever uses a few variables. Space complexity is about memory consumed while the program is running, as input size increases — not the size of the code itself.

Auxiliary Space vs Total Space — the Distinction Your Exam Actually Tests

There is a second, more precise distinction that CBSE and most textbooks expect you to know. The memory needed to simply store the input (the array you were given to work with) is called input space. The extra memory the algorithm creates on top of that input while it works — new lists, extra variables, recursive call frames — is called auxiliary space. When a question asks for the "space complexity of an algorithm," it almost always means the auxiliary space, because the input space is usually unavoidable and identical no matter which algorithm you choose to solve the problem.

Let's make this concrete with numbers. Suppose a CBSE school stores the marks of 40 students in an array, and assume — purely to keep the arithmetic clean, since real memory bookkeeping in languages like Python has extra overhead — that each integer takes 4 bytes, a common assumption in languages like C or Java.

def sum_array(arr):
    total = 0
    for x in arr:
        total += x
    return total

def squares(arr):
    result = []
    for x in arr:
        result.append(x * x)
    return result

The input array of 40 marks occupies 40 × 4 = 160 bytes — this is input space, and both functions need it equally, so it doesn't help us tell them apart. sum_array's auxiliary space is just total and x: 4 + 4 = 8 bytes, and that stays exactly 8 bytes whether the school has 40 students or 4,000 — this is O(1) auxiliary space. squares, however, builds a brand-new list of the same length as the input: for 40 students that's another 160 bytes, but for 400 students it becomes 1,600 bytes, for 4,000 students 16,000 bytes, and for 40,000 students (a large combined exam batch) 1,60,000 bytes — the auxiliary memory grows in direct, ten-times-for-ten-times proportion with n. That's O(n) auxiliary space, exactly like reverse_new_array above.

Reading the Growth: O(1), O(n), and O(n²)

A third growth pattern shows up whenever an algorithm builds a table with two dimensions that both depend on n — for instance, a table of distances between every pair of stations on a railway network with n stations. If there are n stations, a full distance table needs n rows and n columns — n × n = n² entries. This grows far faster than O(n). The graph below plots all three patterns side by side for input sizes from 0 to 8, using the actual functions from this chapter as the labelled examples.

Notice how close the O(n) and O(n²) curves are for small n (they even touch at n = 6 in this illustration) but how sharply the O(n²) curve pulls away as n keeps growing. This is exactly why O(n²) space is dangerous in practice: doubling the input doesn't just double the memory needed, it roughly quadruples it. A distance table for 1,000 railway stations (at 4 bytes per entry) needs 1,000 × 1,000 × 4 = 40,00,000 bytes, about 4 MB. Sounds manageable — but double the network to 2,000 stations, and the table needs 2,000 × 2,000 × 4 = 1,60,00,000 bytes, about 16 MB: four times as much memory for only twice as many stations. An algorithm designer who doesn't notice this quadratic growth can build something that works fine in testing (with a handful of stations) and then fails in production (with thousands).

The Hidden Memory Cost of Recursion

Here is a common misconception worth correcting directly: many students believe recursive functions use no extra memory, since they don't visibly create arrays or lists — the function just "calls itself." This is false. Every time a function calls another function (including calling itself), the computer must set aside a small block of memory called a stack frame to hold that call's local variables and remember where to return control once it finishes. As long as a call hasn't returned yet, its stack frame stays in memory. Consider computing 4! (4 factorial) recursively:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Calling factorial(4) cannot finish computing 4 * factorial(3) until factorial(3) returns a value — so its stack frame must stay alive, waiting. Similarly, factorial(3) must wait for factorial(2), which waits for factorial(1), which waits for factorial(0). At the deepest point of the recursion, all five calls — factorial(4) through factorial(0) — have live stack frames sitting in memory simultaneously, even though the code never wrote a single array. Only once factorial(0) returns 1 does the unwinding begin: factorial(1) computes 1 × 1 = 1 and returns, then factorial(2) computes 2 × 1 = 2, then factorial(3) computes 3 × 2 = 6, then finally factorial(4) computes 4 × 6 = 24 and the whole call stack empties out.

In general, a recursive function that calls itself once per call, reducing n by a fixed amount each time (like factorial(n-1)), builds up roughly n stack frames at its deepest point — O(n) auxiliary space — purely from the mechanics of function calling, regardless of whether it ever touches an array. This is also why deeply recursive functions can crash with a "maximum recursion depth exceeded" or "stack overflow" error even when they use almost no other memory: the stack itself runs out of room. An iterative version of factorial using a simple loop, by contrast, uses only O(1) space, because there is only ever one "frame" — the loop's own variables — active at any time, no matter how large n is.

The Space–Time Trade-off: Finding a Repeated Roll Number

Sometimes the same problem can be solved with different space complexities, and choosing between them means trading memory for speed. Suppose a teacher wants to check whether any roll number was accidentally entered twice while digitising a class list of n students. One approach compares every pair:

def has_duplicate_nested(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                return True
    return False

This uses only two loop counters, i and j, as auxiliary memory — O(1) space — but in the worst case (no duplicate exists) it performs roughly n(n-1)/2 comparisons: for a class of 40, that's 40 × 39 / 2 = 780 comparisons, an O(n²) time cost. A second approach remembers what it has already seen:

def has_duplicate_set(arr):
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)
    return False

Here, each roll number is looked at only once, giving O(n) time — for 40 students, at most 40 checks instead of 780 — but the set seen can grow to hold all n roll numbers in the worst case, costing O(n) auxiliary space (roughly another 160 bytes for our class of 40, at 4 bytes per entry, ignoring the set's internal bookkeeping overhead). Neither version is simply "better" — has_duplicate_nested is the right choice when memory is scarce and the list is small, while has_duplicate_set is the right choice when speed matters and there is memory to spare. Recognising this trade-off, rather than assuming faster is always better, is a core algorithmic skill.

Worked CBSE-Style Problem: Space Complexity of a Distance Table

Question style: Analyse the auxiliary space complexity of the following function, which builds a full n × n grid, and justify your answer.

def create_matrix(n):
    matrix = []
    for i in range(n):
        row = []
        for j in range(n):
            row.append(0)
        matrix.append(row)
    return matrix

Step-by-step reasoning, as you would write it in an exam: the outer loop runs n times (once for each row, i = 0 to n-1). For each of those n iterations, a fresh list row is created, and the inner loop runs n times, appending one element to that row. So each row ends up holding exactly n elements, and there are n rows — giving a total element count of n × n = n². Since the memory used grows in proportion to the square of the input size, the auxiliary space complexity is O(n²). Numerically: for n = 10 (say, ten railway zones), that's 100 stored entries, or 400 bytes at 4 bytes each — trivial. But for n = 1,000 (a national list of stations), that's 10,00,000 entries, or roughly 4 MB — and it keeps growing quadratically, exactly as the graph earlier in this chapter showed.

Check Yourself

• A function accepts an integer n and always returns a fixed 9×9 Sudoku grid filled with zeros, regardless of the value of n. What is its space complexity, and why is this a trick question about the difference between "a table exists" and "a table that scales with the input"?
• Rewrite squares(arr) from this chapter so that it modifies arr in place (each element replaced by its own square) instead of building a new list. What auxiliary space complexity does your version achieve, and what did it cost you in terms of keeping the original values?
• A recursive function sum_list(arr, i) adds up elements from index i to the end of a list of length n by calling itself on i + 1 until i == n. Without writing the code, state its auxiliary space complexity and explain your reasoning using the idea of stack frames from this chapter.
• Between has_duplicate_nested and has_duplicate_set, which would you choose for checking duplicate Aadhaar-linked IDs across 5 crore records on a server with plenty of RAM, and which would you choose for the same check running inside a low-memory embedded device at a small polling booth? Justify using both time and space complexity.
• True or false, and correct the statement if false: "Space complexity of a program is measured by counting the number of lines in its source code."

Summary

• Space complexity describes how the extra memory a program needs grows as its input size n grows — it is separate from, and just as important as, time complexity.
• Total space = fixed part (constant, independent of n) + variable part (scales with n). Most questions ask about auxiliary space: the extra memory used beyond storing the input itself.
• O(1) space means the extra memory stays constant regardless of input size (e.g. sum_array, reverse_in_place, the nested-loop duplicate check).
• O(n) space means extra memory grows directly proportional to input size (e.g. squares, reverse_new_array, the set-based duplicate check, and — importantly — simple linear recursion, because each call adds a stack frame).
• O(n²) space appears when a data structure has two dimensions that both scale with n, such as an n × n distance or adjacency table; it grows dangerously fast, roughly quadrupling when n doubles.
• Recursion is never "free" in memory: every unfinished call keeps a stack frame alive, so deep recursion can consume O(n) space and even crash with a stack overflow, despite never explicitly creating an array.
• When two algorithms solve the same problem with different space and time costs, neither is universally "correct" — the right choice depends on whether memory or speed is the scarcer resource in the situation you're designing for.