Space complexity and amortised cost

Why memory matters too

Memory is limited. A phone app, a small cloud server or an online judge with a 256 MB limit will crash or be killed if your code builds huge lists it does not need. So interviewers often ask two questions: how much time, and how much space?

Space complexity is how the extra memory your code uses grows with n. "Extra" (also called auxiliary space) means memory beyond the input itself. Most interviewers do not count the input, and many do not count the output you must return; if unsure, say which you mean.

def total(nums):              # O(1) extra space: one number
    s = 0
    for x in nums:
        s += x
    return s

def squares(nums):            # O(n) extra space: a new list of n items
    return [x * x for x in nums]

print(total([1, 2, 3]), squares([1, 2, 3]))   # Output: 6 [1, 4, 9]

In-place algorithms

An in-place algorithm changes the input directly and uses only a few extra variables, O(1) extra space. Reversing a list by swapping the two ends and moving inwards is in place. Building a reversed copy with nums[::-1] is not: it creates a whole new list, O(n) extra space.

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

a = [1, 2, 3, 4]
reverse_in_place(a)
print(a)    # Output: [4, 3, 2, 1]

Recursion uses stack space

When a function calls itself, each call that has not finished waits in memory on the call stack, in a "frame" holding its local variables. If the recursion goes n levels deep, it uses O(n) space even if it creates no lists. Python stops very deep recursion with a RecursionError; the default limit is about 1,000 levels (sys.getrecursionlimit() returns 1000 by default).

def total_rec(nums, i=0):
    if i == len(nums):
        return 0
    return nums[i] + total_rec(nums, i + 1)

print(total_rec([5, 6, 7]))   # Output: 18

Amortised cost: why append is fast

A Python list is a dynamic array: a block of memory with some spare room at the end. append puts the new item in the spare room, which is O(1). When the room runs out, Python allocates a bigger block and copies every item across, which is O(n) for that one append.

Amortised cost means the average cost per operation over a long sequence of operations. Suppose the capacity doubles each time it fills: 1, 2, 4, 8 … To reach n items, the copies add up to 1 + 2 + 4 + … which is less than 2n. So n appends cost O(n) in total, which is O(1) amortised per append. CPython actually grows by a smaller factor (roughly an eighth extra), but any growth by a constant factor gives the same O(1) amortised result.

Trading memory for time

Often you can spend memory to save time. A set of seen items costs O(n) memory but turns O(n²) duplicate checks into O(n). Caching, also called memoisation, stores answers you have already computed so you never compute them twice.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(80))   # Output: 23416728348467685

Common mistakes

• Forgetting the recursion stack. Fix: count the maximum depth of recursion as space.
• Slicing inside recursion or loops. nums[1:] copies n − 1 items each time, so a recursive sum written with slices is O(n²) time and space. Fix: pass an index instead.
• Calling something in place when it builds a new list. Fix: in-place code changes the list you were given and does not create another of size n.
• Thinking amortised O(1) means every single append is O(1). Fix: one append in many can be O(n); only the average is O(1).
• Rebinding instead of changing: nums = nums[::-1] inside a function does not change the caller's list. Fix: change items by index, or write nums[:] = … if a copy is acceptable.