Space Complexity & Amortized Analysis

Algorithms & Complexity

Chapter 8 · Space Complexity & Amortized Analysis

Every chapter so far measured time. This chapter measures the other resource that matters just as much in practice — memory — and then covers a genuinely different kind of question: what happens when a single operation is occasionally expensive, but only rarely?

Auxiliary Space vs. Input Space

The key distinction

Input space — the memory needed just to store the input — is usually not counted, since it's given regardless of the algorithm. Auxiliary space is the extra memory an algorithm allocates beyond that input. Space complexity almost always means auxiliary space.

Bubble sort (Chapter 7) sorts in place — a couple of temporary variables for swapping, regardless of array size: O(1) auxiliary space, even though it touches all O(n) of the input.

Merge Sort's Hidden Cost: O(n) Space

A real time-vs-space tradeoff, not a free upgrade

Merge sort's merging step (Chapters 5–7) needs a temporary array to hold the merged result before copying it back — O(n) auxiliary space. Bubble sort's O(n²) time comes with only O(1) space; merge sort's much better O(n log n) time comes at the cost of genuine extra memory. Neither algorithm is simply "better" in every dimension — this is exactly the kind of tradeoff a real engineering decision has to weigh.

Recursive Call Stack Space

Every recursive call adds a frame to the call stack, and that frame occupies real memory until the call returns. Chapter 5's own countdown function makes n nested calls before hitting its base case — O(n) auxiliary space, purely from stacked call frames, even though it allocates nothing else.

A genuinely non-obvious result: naive Fibonacci uses only O(n) space

Chapter 5's naive Fibonacci makes an exponential total number of calls — but at any single moment, the call stack only holds calls along one path from the root down to a base case, since recursion explores depth-first: one branch fully unwinds before its sibling begins. Verified directly: fib(20) makes 21,891 total calls over its full execution, yet its call stack never exceeds depth 19. Time (total work done) and space (maximum simultaneous memory) are genuinely different measurements — a function can be catastrophically slow while still being memory-cheap.

Time and Space Side by Side

Algorithm	Time	Space	Why
Bubble sort	O(n²)	O(1)	Sorts in place, a few temp variables
Merge sort	O(n log n)	O(n)	Temporary arrays needed for merging
Countdown (Ch.5)	O(n)	O(n)	Call stack depth grows with n
Naive Fibonacci (Ch.5)	O(2ⁿ)	O(n)	Exponential total calls, but only linear stack depth at once

Amortized Analysis: The Dynamic Array

A dynamic array (like Python's own list) grows by doubling its capacity whenever it fills up — copying every existing element into a new, larger array. That single resize is O(n). But it doesn't happen on every append.

Amortized analysis asks a different question

Not "what does the worst single operation cost," but "what's the average cost per operation across a long sequence of them" — even when some individual operations are genuinely expensive.

Simulating 16 appends, starting from capacity 1 and doubling each time it fills:

Resize event	Elements copied
Capacity 1 → 2	1
Capacity 2 → 4	2
Capacity 4 → 8	4
Capacity 8 → 16	8

Total copy cost: 1+2+4+8 = 15. Plus 16 individual element placements: 15 + 16 = 31 total operations for 16 appends — ≈1.94 operations per append, even though the single most expensive append (the one triggering the capacity-8-to-16 resize) cost 9 operations on its own.

The ratio stays near a small constant as n grows — O(1) amortized

At n=100: 227 total operations, ≈2.27 per append. At n=1,000: 2,023 total operations, ≈2.02 per append. The per-append cost doesn't grow with n — it hovers around 2, confirming O(1) amortized time, even though any single append can, rarely, cost O(n).

Space & Amortized Analysis in Code

def simulate_dynamic_array(n):
    capacity, size, total_ops = 1, 0, 0
    for _ in range(n):
        if size == capacity:
            total_ops += capacity   # cost of copying on resize
            capacity *= 2
        total_ops += 1              # cost of placing the new element
        size += 1
    return total_ops

n = 1000
print(simulate_dynamic_array(n) / n)  # ~2.02 -- O(1) amortized

def fib_max_depth(n, depth=0, tracker=None):
    if tracker is None:
        tracker = [0]
    tracker[0] = max(tracker[0], depth)
    if n > 1:
        fib_max_depth(n - 1, depth + 1, tracker)
        fib_max_depth(n - 2, depth + 1, tracker)
    return tracker[0]

print(fib_max_depth(20))  # 19 -- linear space despite exponential total calls

Hands-On Exercises

Exercise 1

A function reverse_new(arr) builds and returns a brand-new list containing arr's elements in reverse order. A second function reverse_in_place(arr) swaps elements within the same array using two index pointers moving toward each other. State the auxiliary space complexity of each, and explain the difference using this chapter's own input-space-vs-auxiliary-space distinction.

📄 View solution

Exercise 2

Using this chapter's own dynamic-array-doubling method, compute the total operation count and the amortized cost per append for n = 32 appends (starting from capacity 1, doubling at each resize). Show each resize event's own copy cost.

📄 View solution

Exercise 3

Explain, in your own words, why naive recursive Fibonacci uses only O(n) auxiliary space despite making O(2ⁿ) total function calls over its full execution. Ground your answer in this chapter's own distinction between total work done (time) and maximum simultaneous memory in use (space).

📄 View solution

Chapter 8 Quick Reference

Auxiliary space (extra memory beyond the input) is what space complexity almost always measures — input space is usually not counted
Recursive calls consume stack space proportional to recursion depth, not total calls made — naive Fibonacci is O(2ⁿ) time but only O(n) space
Merge sort's O(n log n) time comes with a real O(n) space cost, versus bubble sort's O(1) space at O(n²) time — a genuine tradeoff, not a strict improvement
Amortized analysis: the average cost per operation across a long sequence, even when individual operations vary wildly
Dynamic array doubling: occasional O(n) resizes, but O(1) amortized time per append — verified directly (≈2 operations per append, staying constant as n grows)
Next chapter: Beyond polynomial time — exponential growth and a taste of P vs. NP