Space complexity: recursion stack vs buffers

Intermediate Asymptotics & empirical timing

Created by Pavel · 29.04.2026 at 19:08 UTC

Auxiliary space counts extra memory beyond the input itself: recursion stack frames, temporary buffers for merges, copies of columns, intermediate tensors. An algorithm can be O(n) time but O(n) extra space if it allocates a result array; or O(log n) stack depth for balanced recursive divide-and-conquer.

Iterative binary search uses O(1) extra indices; recursive binary search uses O(log n) stack frames in typical implementations. In-place algorithms try for O(1) extra space but may be harder to read.

In pandas/NumPy, “copy” vs “view” semantics interact with this: accidental df.copy() doubles resident memory for wide tables.

Space complexity (intro): [1].

Sources

[1]https://wiki.python.org/moin/TimeComplexity Return to text

University approvals: 0

Tasks

Question 1

Typical auxiliary space for iterative binary search on a list (only index variables, no copied input) is:

Hint

A handful of integer indices.

O(1)

O(log n)

O(n)

O(n log n)

Question 2

You allocate out = list(xs) then modify out in a pipeline stage. Compared with in-place mutation of xs, what is the typical extra space scaling in the size of xs?

Hint

A full duplicate list stores every element again.

O(1)

O(log n)

O(n)

O(1) because Python uses views

Question 3

rev_copy(xs) returns a new list with elements of xs in reverse order. Do not mutate xs.

Hint

Slicing [::-1] or reversed()+list both work.

def rev_copy(xs):
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Asymptotics & empirical timing
Difficulty: Intermediate
Completed: 0 users

Creator

Pavel