Amortized and Space Complexity

1. What It Is and Why It Exists

Amortized complexity is the average cost per operation across a worst-case sequence of operations, when an occasional expensive operation is paid for by many cheap ones. It exists because reporting only the single worst operation overstates the real cost. The canonical case is Python's list.append: most appends are O(1), but when the backing array is full it allocates a bigger array and copies everything (O(n)). If you doubled the array, that O(n) copy happens only every ~n appends, so the cost averaged over the sequence is O(1) amortized — the expensive resize is "amortized away" by the cheap appends that follow.

Space complexity measures memory use as a function of input size. Here we report auxiliary space: memory used beyond the input itself. State whether returned output is included, since output storage can be much larger than the working state. The non-obvious part candidates miss: the call is space. A that goes n deep is O(n) space even if it allocates no array, and that is exactly the kind of thing an interviewer pushes on.

Cheap appends pay for occasional copies

Doubling makes costly resizes rare: eight appends copy seven items in total, giving constant amortized work per append.

The empty buffer has room for one item, so the other slots are faded.

Text version

The empty buffer has room for one item, so the other slots are faded.
Appending ten needs only one write because there is room.
Appending twenty fills a new slot after capacity doubles and one item is copied.
Appending thirty doubles capacity to four and copies two items.
Appending forty needs no copy, because slot three is still free.
Appending fifty doubles capacity to eight and copies four items.
Appending sixty needs no copy.
Appending seventy also needs no copy.
Appending eighty fills the buffer without another copy.
Seven copies plus eight writes make fifteen, under two per append, so each append is constant time amortized.

Quick check

A backend service uses a dynamic array (like Python's list) to buffer incoming log entries. Most append operations run in O(1), but occasionally the array must resize, copying all existing entries — an O(n) operation. How should the overall cost of appending n log entries be characterized, and why?

2. Operations and Complexity

Concept	Per-op (naive view)	Amortized / Actual	Notes
Dynamic array `append`	`O(n)` on resize	`O(1)` amortized	Geometric growth (doubling) is the key
`n` appends total	—	`O(n)` total	Sum of a geometric series, not `O(n^2)`
Hash table `insert`	`O(n)` on rehash	`O(1)` average amortized	Geometric growth plus well-distributed hashes
Iterative algorithm space	—	`O(1)`–`O(n)` aux	Count only extra allocations
Recursion space	—	`O(depth)`	Stack frames; balanced tree → `O(log n)`, skewed → `O(n)`

The "why it works" intuition for amortized O(1) append: with geometric (doubling) growth, the total copy work over n inserts is 1 + 2 + 4 + ... + n < 2n, so total cost is O(n) and the per-op average is O(1). (Linear growth — adding a constant chunk — would make total work O(n^2), which is why doubling matters.)

Interviewers probe two things: (1) "is that O(1) or O(1) amortized?" — say "amortized" and explain the resize; (2) "what's the space complexity?" — answer in auxiliary terms and explicitly include depth.

Doubling keeps total work linear

Fixed-chunk growth costs quadratic total work; doubling costs linear total work and constant amortized work per append.

Fixed-chunk growth costs quadratic total work as the number of appends grows.

Text version

Fixed-chunk growth costs quadratic total work as the number of appends grows.
Doubling makes the copied sizes a geometric sum, so total work stays linear.
Dividing linear total work by the number of appends gives constant amortized cost per append.
As n grows to thirty-two, n squared reaches one thousand twenty-four, while n reaches only thirty-two.
Running the doubling algorithm for thirty-two appends copies thirty-one items, less than sixty-four.

3. Implementation

The dynamic array below makes resizing visible; the two sum functions then show how changes auxiliary space even when both functions compute the same result. The array starts empty, and n is the number of appended items.

# Amortized O(1) append, demonstrated by the doubling that hides the O(n) copy.
class DynamicArray:
    def __init__(self):
        self._cap = 1
        self._n = 0
        self._buf = [None] * self._cap

    def append(self, x):
        if self._n == self._cap:        # rare: triggers an O(n) copy
            self._cap *= 2              # DOUBLE -> resize cost amortizes to O(1)
            new_buf = [None] * self._cap
            for i in range(self._n):    # the O(n) copy ...
                new_buf[i] = self._buf[i]
            self._buf = new_buf
        self._buf[self._n] = x          # ... paid for by ~n cheap O(1) appends
        self._n += 1
    # n appends => total copy work 1+2+4+...+n < 2n => O(n) total => O(1) amortized.

# Space complexity: iterative is O(1) auxiliary; recursion costs O(depth).
def sum_iter(nums):
    total = 0
    for x in nums:        # O(1) extra space, regardless of n
        total += x
    return total

def sum_rec(nums, i=0):
    if i == len(nums):    # recursion goes n deep -> O(n) STACK space,
        return 0          # even though no array is allocated.
    return nums[i] + sum_rec(nums, i + 1)

In a real interview you do not implement a dynamic array — Python's built-in list already gives amortized-O(1) append. You cite the amortized argument: "list.append is amortized O(1) because CPython over-allocates geometrically."

The same sum uses different auxiliary space

The loop reuses one frame, while recursion retains a frame for each pending call, giving linear stack space.

The input contains three, one, and four; only the main frame is active.

Text version

The input contains three, one, and four; only the main frame is active.
The loop starts with a zero total and one function frame.
Adding all three items gives eight without growing the call stack.
The loop prints eight and uses constant auxiliary space.
Recursion starts at index zero, and this call pushes its own stack frame.
Index one adds another frame while the first call waits.
Index two adds a third frame while earlier calls still wait.
The base case returns zero, with four recursive frames for three items, so stack space grows linearly.
The deepest pending addition returns four.
The next frame adds one and returns five.
The first frame adds three and returns eight.
Recursion prints the same eight, but its auxiliary stack space is linear.

Quick check

A backend service uses a recursive function to traverse a deeply nested JSON configuration tree with up to 10,000 nodes. A colleague suggests replacing it with an iterative version using an explicit stack. From a space-complexity perspective, what is the key difference between the two approaches?

4. When to Reach for It

For list.append, report amortized O(1) because resizing is occasional. For dict/set insertion, report average amortized O(1) because collisions also matter. A collections.deque supports O(1) operations at either end without shifting the other elements.
When the interviewer asks "is appending n items O(n) or O(n^2)?" → O(n) total, because of geometric growth.
Whenever you give a time complexity → immediately give the auxiliary space complexity in the same breath.
When you write → state space as O(max depth) and identify whether that depth is log n (balanced) or n (skewed/linear).

Quick check

A backend service builds a result list by calling list.append() inside a loop that runs n times. What is the correct time complexity to report for the entire append sequence, and why?

5. Common Pitfalls

Saying n appends is O(n^2). Forgetting the geometric-growth argument and counting each resize at full price.
Confusing amortized with average-case. Amortized is a guarantee over any sequence (no probability); average-case depends on input distribution. Quicksort is average-O(n log n); dynamic-array append is amortized-O(1).
Leaving the space convention unstated. Distinguish total memory from auxiliary memory; count the input only in the former, and say whether returned output is included.
Forgetting space. Claiming an in-place recursive algorithm is O(1) space when its is O(n) deep.
Claiming amortized O(1) for linear growth. Growing by a fixed chunk instead of doubling makes append amortized O(n) — the doubling is load-bearing.

Quick check

A backend engineer implements a dynamic buffer that grows by a fixed chunk of 100 elements every time it runs out of space, rather than doubling its capacity. They claim appending n elements is amortized O(1) per append. Why is this claim incorrect?

6. Interview Cheat Sheet

"list.append is amortized O(1) because capacity grows geometrically. Doubling is the simple example shown here; Python does not need to double to obtain O(n) total time for n appends."
"Amortized is a worst-case guarantee over a sequence with no probability; average-case depends on the input distribution — they are not the same."
"I report auxiliary space, and depth counts: a balanced is O(log n) space, a skewed one is O(n)."
"In-place doesn't always mean O(1) space — if it recurses n deep it's O(n) on the ."

Follow-ups:

"Why doesn't appending n items cost O(n^2)?" — Geometric growth: total copy work is a geometric sum such as 1 + 2 + 4 + ..., less than 2n, so O(n) total, O(1) amortized.
"Difference between amortized and average-case?" — Amortized: deterministic guarantee over a sequence. Average: expectation over an input distribution. Resize → amortized; quicksort → average.
"Your is recursive — what's the space?" — O(h) for the call where h is the recursion depth (O(n) worst case for a skewed tree / long path), plus any visited set.

Tier 1 · Foundations

Complexity

Linear Structures

Hierarchical Structures

Tier 2 · Patterns

Tier 3 · Dynamic Programming

1. What It Is and Why It Exists

2. Operations and Complexity

3. Implementation

4. When to Reach for It

5. Common Pitfalls

6. Interview Cheat Sheet

Reading

On this page

My notes

Glossary history