Space and hidden costs

Space complexity

Every algorithm uses memory as well as time, and the two are measured the same way: as a function of the input size, simplified with Big-O.

The memory that counts is usually the extra memory, sometimes called auxiliary space: what the algorithm needs beyond its input and output. The input has to be stored anyway, so it says nothing about the algorithm. The trace above reverses a list using two indexes and a temporary for each swap. However long the list, that is the same few values, so the extra space is O(1). The one-liner a[::-1] produces the same result but builds a new list of n references, which is O(n) extra space.

For a single call on a laptop, 8 MB hardly matters. On a server running the function for 1,000 requests at once, it is 8 GB. Memory is often what limits how much work a machine can do in parallel, and running out of it fails much harder than running slowly.

Where memory hides

Like hidden loops, extra memory often sits in innocent-looking code:

• Copies. Slicing, sorted(), list(x), string concatenation, and converting between types all build new objects of size n.
• Helper structures. A set of seen values, a dictionary of counts or a queue of pending work grows with the input. Using one is often the right choice, but it is O(n) space.
• Recursion. Each active function call keeps a stack frame with its arguments, locals and return address. A recursion that goes n levels deep holds n frames at once: O(n) space, even if each frame is small. Python stops at 1,000 levels by default, and a typical thread stack of a few megabytes overflows somewhere in the tens of thousands of frames.
• Over-allocation. Dynamic arrays and hash tables keep spare capacity so that they can grow cheaply, often up to twice what they hold.

Trading memory for time

Many problems can be solved faster by spending memory, and choosing between the two is a real design decision. Take "does this list contain a duplicate?":

*If the sort itself works in place; Python's and Java's object sorts allocate up to n/2 extra.

The hash set is usually the right answer: memory is cheap compared with quadratic time. But not always. If the list is enormous, or the function runs inside a memory-constrained process, the sorting version may be the only one that fits. Many interview questions ask for exactly this second option, an O(1)-space solution that uses the structure of the input instead of a helper. The practice problems for this lesson are two of them.

The same trade appears at every scale: caches keep results to avoid recomputing them, indexes in a database spend disk space to make queries fast, and dynamic programming, later in this track, stores the answers to subproblems so it never solves one twice.

Costs Big-O leaves out

Big-O drops constant factors on purpose, but the constants are real, and some are large:

• The language. The same loop can be 30 to 100 times slower in an interpreted language than in a compiled one.
• Memory access. As the first module showed, a cache miss costs around a hundred times as much as a hit. An O(n) walk over a linked list can be ten times slower than an O(n) walk over an array.
• Allocation. Creating objects costs time to allocate them and, in garbage-collected languages, time to collect them later. An algorithm that allocates inside its inner loop pays that on every step.
• Copying. Building a string with s = s + c in a loop copies everything built so far on every pass, so n appends cost O(n²) in total. A builder or a list joined at the end costs O(n).
• Input and output. Reading a file or calling over a network costs thousands to millions of times more than a memory access, and it often dominates everything else.

None of these change which algorithm scales. All of them change how fast it actually runs.

Measuring memory for real

Big-O space tells you how memory grows; tools tell you how much a program actually uses. In Python, tracemalloc reports the peak memory a block of code allocated, and sys.getsizeof gives the size of one object (but not of the objects it refers to). In Java, a profiler such as VisualVM or the JDK Flight Recorder shows heap usage over time. On any system, the peak resident memory of a process, shown by /usr/bin/time -v on Linux, is the number that decides whether it fits on a machine.

Measure on realistic input sizes. A function that allocates O(n) extra memory looks free on a test with ten items and only shows its cost when n reaches millions, which is exactly when it matters.

Saying it in full

A complete description of an algorithm's cost names both resources and the case: "O(n) time and O(1) extra space", "O(n log n) expected time, O(log n) stack space". With time, space, the three cases and the constants Big-O hides, you have the full vocabulary this track uses. The next module applies it to the simplest structure of all, the array.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Space and hidden costs from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

def reverse_in_place(a):
    i, j = 0, len(a) - 1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1

#include <vector>
#include <algorithm>
 
long long processArrayInvariants(std::vector<int>& nums) {
    long long acc = 0;
    int lo = 0, hi = static_cast<int>(nums.size()) - 1;
    while (lo <= hi) {
        acc += nums[lo];
        if (lo < hi) acc += nums[hi];
        ++lo; --hi;
    }
    return acc;
}

public class ArrayInvariantSolver {
    public static long processArrayInvariants(int[] nums) {
        long acc = 0;
        int lo = 0, hi = nums.length - 1;
        while (lo <= hi) {
            acc += nums[lo];
            if (lo < hi) acc += nums[hi];
            lo++; hi--;
        }
        return acc;
    }
}

def process_array_invariants(nums: list[int]) -> int:
    acc = 0
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        acc += nums[lo]
        if lo < hi:
            acc += nums[hi]
        lo += 1
        hi -= 1
    return acc

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.