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 the extra memory an algorithm uses as a function of input size. The number interviewers want is auxiliary space — memory you allocate beyond the input itself — because the input is a sunk cost the caller already paid. The non-obvious part candidates miss: the recursion call stack is space. A recursion 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.

2. Operations and Complexity

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 recursion depth.

3. Implementation

There is no structure to build; the skill is computing the amortized and space bounds correctly.

Copy
# 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."

4. When to Reach for It

• When you use list.append, dict/set insertion, or collections.deque in a loop → claim amortized O(1), not O(1), and be ready to justify it.
• 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 recursion → state space as O(max recursion depth) and identify whether that depth is log n (balanced) or n (skewed/linear).

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).
• Reporting total space instead of auxiliary. Counting the input array as your space cost — interviewers want the extra memory.
• Forgetting recursion stack space. Claiming an in-place recursive algorithm is O(1) space when its stack 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.

6. Interview Cheat Sheet

• "list.append is amortized O(1): the array doubles on resize, so the O(n) copy is paid back by the next n cheap appends — n appends is O(n) total."
• "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 recursion depth counts: a balanced recursion 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 stack."

Follow-ups:

• "Why doesn't appending n items cost O(n^2)?" — Geometric growth: total copy work is 1 + 2 + ... + n < 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 DFS is recursive — what's the space?" — O(h) for the call stack where h is the recursion depth (O(n) worst case for a skewed tree / long path), plus any visited set.