3 of 32 · 5 min

The other resource

Time is not the only thing an algorithm spends. A solution that runs in a second and needs 8GB of memory does not run at all on a machine with 4.

Space complexity is counted the same way as time: how does the memory grow as the input grows.

What counts

The convention is to count extra space, not the input itself. An algorithm that sorts an array of a million numbers in place is O(1) extra, even though a million numbers are sitting there, because they were given to you.

python

def total(nums):          # O(1) extra: one accumulator
    s = 0
    for n in nums:
        s += n
    return s

def doubled(nums):        # O(n) extra: a new list the size of the input
    return [n * 2 for n in nums]

Recursion is not free

This is the one people miss. Every recursive call holds a stack frame until it returns.

python

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

O(n) time and O(n) space, because n frames are open at the deepest point. The loop version is O(1) space and identical otherwise.

For a tree, the depth is the height: O(log n) on a balanced tree, O(n) on a degenerate one, which is the same height argument as everywhere else.

The trade is real and goes both ways

Approach	Time	Space
Check duplicates with nested loops	O(n squared)	O(1)
Check duplicates with a hash set	O(n)	O(n)
Sort then scan	O(n log n)	O(1) if sorted in place

None of these is the right answer. The right answer depends on whether the constraint is a slow machine or a small one, and an interviewer asking "can you do it without extra space" is asking you to move along this table deliberately.

Sorting, compared on space

Algorithm	Extra space
Merge sort	O(n)
Quicksort	O(log n) for the call stack
Heapsort	O(1)
Insertion sort	O(1)

Merge sort needs somewhere to merge into, which is the main reason quicksort is usually preferred despite its worse worst case.