Space complexity describes how an algorithm's memory requirement grows with input size. A backtest may read every cashflow once yet exhaust memory by keeping every intermediate result. Asking what must stay in memory is a separate question from asking how many operations run. The formal worst-case viewpoint takes the maximum requirement over inputs of a given size. NIST's definition makes that quantifier explicit.
Say which memory you are counting
Let be the number of cashflows. Before giving a Big O bound, state the storage boundary:
| Component | What it includes |
|---|---|
| Input space | The cashflows already held in memory. |
| Output space | Results that must be returned and retained, such as a complete balance history. |
| Auxiliary space | Working storage beyond the input and output, including temporary objects and active function calls. |
| Total space | All distinct storage within the chosen boundary that is live at the same time. |
Here, auxiliary excludes output. Some descriptions group output into “extra space”, so an unqualified space bound can be ambiguous. Shared objects also count once, even if several names refer to them.
The relevant quantity is peak live storage, not the total of every allocation ever made. Two large arrays used one after another can reuse memory; two arrays needed simultaneously cannot. A single variable can refer to a million-element list, so counting variable names is insufficient.
One balance or every balance?
Consider fictional cashflows of 30, −10 and 5 currency units, arriving in that order. With an initial balance of zero, the running balances are 30, 20 and 25. Two requirements lead to different storage choices:
def final_balance(cashflows: list[int]) -> int:
"""Return the ending balance without retaining its history."""
total = 0
for cashflow in cashflows:
total += cashflow
return total
def balance_history(cashflows: list[int]) -> list[int]:
"""Return the balance after each cashflow."""
totals = []
total = 0
for cashflow in cashflows:
total += cashflow
totals.append(total)
return totals
cashflows = [30, -10, 5]
print(final_balance(cashflows))
print(balance_history(cashflows))
print(cashflows)
# 25
# [30, 20, 25]
# [30, -10, 5]Neither function changes the input list. The first keeps one running aggregate and returns one result. The second retains balances because that is its requested output.
The aggregate is replaced; the history accumulates. Boxes show retained aggregate or output values after each event, not Python object sizes or all working storage.
Under a word model in which each cashflow and balance fits in a fixed-size word, the classifications are:
| Requirement, with the existing input list retained | Input | Output | Auxiliary | Total peak |
|---|---|---|---|---|
| Ending balance | ||||
| Complete balance history |
These are also tight orders under the stated model. Both functions have linear time complexity, but only the history requires a growing output. Calling the first “constant space” is accurate for auxiliary space, not for its total memory while the input list remains resident.
If cashflows instead arrive from a source that keeps only a bounded input buffer, the ending-balance calculation can use constant total storage within that streaming boundary. Converting the source into a list first would remove that advantage. Materialising the entire history still takes linear output space; emitting balances one at a time only avoids that cost if the consumer also avoids retaining them all.
What the word model hides
Python's integers have unlimited precision. One integer variable therefore does not mean a constant number of bytes for values allowed to grow without bound. For an exact sum of bounded integer cashflows, the balance's bit length can grow with ; if input magnitudes are also unbounded, their bit lengths belong in the analysis too. Fixed-width numerical types bound storage per value but introduce range and precision constraints. The Python example above demonstrates the storage pattern, with small exact integers; it does not establish a universal byte bound. See Python's numeric-type contract.
Other storage can hide behind compact code:
- Recursion. A chain of recursive calls keeps active calls alive until they return. If the maximum depth is and each call retains constant-size state, the stack contributes auxiliary space, even without an explicit list. Python exposes a recursion-depth limit through its interpreter-stack documentation.
- NumPy expressions. A compound array expression can create full-size temporaries. Reusing an output buffer can reduce peak storage, but shape, dtype and overlap matter;
out=is not a universal promise of zero temporary memory. NumPy's ufunc documentation describes both output allocation and overlap-related copies.
Asymptotic analysis identifies the growth pattern. Actual capacity planning also needs the representation, buffers and runtime overhead. A shallow
sys.getsizeof(container) reading omits the objects it refers to, as Python's documentation warns. It is not a whole-program peak-memory measurement.For the formal meaning of upper and tight bounds, continue with Algorithms, Growth Rates, and Asymptotic Notation — public preview; full lesson requires membership.