B2.4.1 · Efficiency and memory

Auxiliary space

Python · step by step

Auxiliary space

Example

Compare a running total with a growing copy of the input.

Select Play or Next line to follow Python execution.

Python implementation

The highlight marks the next line to execute. Values show the state before that line.

1def auxiliary_space(items, copy_input):2    total = 03    working = []4    for value in items:5        total = total + value6        if copy_input:7            working.append(value)8    return total

Speed

Execution progress

The supplied list is input space. total and value occupy a fixed number of slots in our classroom model. The copy grows to n elements. Without the copy: O(1) auxiliary space; with it: O(n). Both scans take O(n) time.

Keep exploring

Return to the algorithm efficiency lesson →

Constant growth · O(1)
Linear growth · O(n)
Logarithmic growth · O(log n)
Quadratic growth · O(n²)

All B2.4 animations →

All practice & resources →