Space Complexity Accounting for Recursion, Auxiliary Buffers and Output

Space bounds carry a longer list of implicit conventions than time bounds do, because “how much memory this algorithm uses” is not one quantity. It is at least three: the depth of the call stack at its deepest point, the size of the explicit data structures allocated to get the work done, and the size of the result the caller must be handed. Most arguments about whether a routine is “O(1) space” are really arguments about which of the three is being counted.

The three buckets and the convention that picks them

The usual convention for algorithm analysis counts auxiliary space: memory beyond the input and beyond the output that the algorithm is required to produce. Under that convention an in-place array reversal is O(1) space, since it holds a single temporary, and a merge sort is O(n) because the merge needs a buffer holding the elements of both halves.

The convention is a choice, and the choice changes the answer. A routine that fills an output array of n elements and holds one O(1) temporary is Θ(1) auxiliary space and Θ(n) total space; quoted as O(1) by a caller counting only scratch, it appears to beat one that writes into a caller-provided buffer, although both need the same n cells of result storage. The output-sensitive convention, which counts total memory including the result, is the right one when the question is whether the routine fits in a fixed memory budget, and the auxiliary convention is the right one when the question is whether the routine adds pressure on top of a result the caller wanted anyway.

There is a third convention in use for streaming algorithms: the input arrives one element at a time, the algorithm sees it once, and space means the working memory kept between elements. Under that convention, a routine that stores all n inputs and then processes them is Θ(n), and the ordering guarantees of one-pass algorithms become interesting questions in their own right.

Whichever convention is used, it has to be applied consistently, because mixing them produces comparisons that mean nothing. The cleanest phrasing names the convention: “Θ(1) auxiliary space, Θ(n) total, Θ(log n) stack depth” is a complete description of a bottom-up heap sort or of an in-place quicksort on a balanced input.

Stack depth is a space cost that hides in a time analysis

Recursion consumes stack frames, and the number of frames live at the deepest point of the recursion is exactly the height of the recursion tree. That height is not the same as the number of calls. A routine that makes two recursive calls in sequence from one frame has n total calls and a stack depth equal to the depth of the deepest chain, which for a balanced split is Θ(log n). A routine that makes the second call before the first returns has the same total call count and a stack depth of Θ(log n) too, but a routine that recurses on a subproblem of size n − 1 has depth Θ(n) and can overflow the stack on inputs that a time analysis would call trivial.

The distinction matters most for the two classic divide-and-conquer routines:

• Merge sort recurses on both halves and returns, so its live stack is the depth of the tree, Θ(log n), plus the Θ(n) merge buffer, giving Θ(n) total auxiliary space.
• Quicksort recurses on one side and then the other. If it recurses first on the larger side, the smaller side’s frames are pushed while the larger side is still being processed, and the stack depth is Θ(n) in the worst case. Recursing on the smaller side first bounds the stack to O(log n) even when the pivot choices are bad, because each level then at least halves the problem being held open.

That last fact is worth stating precisely because it is a case where an algorithmic change confined to one line of code changes a complexity class. Recursing on the smaller partition and looping on the larger means every nested frame holds a problem at most half the size of its parent’s, so at most log₂ n frames can be live at once. The running time is unchanged; the space bound drops from Θ(n) to Θ(log n).

Stack frames are not free in the model either. Each frame holds a return address, saved registers, parameters and locals, and in a typical 64-bit calling convention a frame occupies on the order of tens of bytes even for a trivial function. A recursion with depth 10⁶ therefore costs tens of megabytes of stack, which is why a Θ(n)-depth recursion over a linked list of that length is a practical failure even though its “space” in the textbook sense is unremarkable. Implementations cap the stack, the main thread’s stack is a fixed mapping sized at process start, and threads get a configurable stack size, and exceeding it terminates the process rather than raising a catchable error in most environments.

When the compiler removes the stack

Tail calls are the standard case where the counted stack depth differs from the source-level one. A call is in tail position if its result is returned immediately, so the caller’s frame has nothing left to do. An implementation that performs tail call elimination reuses the caller’s frame for the callee, and a chain of tail calls becomes a loop with a constant number of live frames.

Languages and runtimes differ sharply in whether this happens. Scheme requires proper tail calls as part of the language definition, so a tail-recursive loop runs in constant space by specification. Common Lisp implementations typically do the same. Rust, C and C++ compilers perform the elimination as an optimisation in release builds, typically enabled at optimisation levels above the default, but do not guarantee it, so relying on it for space bounds is not portable. The JVM does not perform general tail call elimination, because the stack-walking semantics of exceptions and debuggers depend on the presence of the frames; the invokedynamic-based mechanism in JSR 292 provides a tail call primitive for language implementers rather than a guarantee for ordinary calls. Python and Ruby limit recursion depth explicitly and raise an error when the limit is passed.

The consequence for analysis is that a recursive formulation and its iterative equivalent can have different asymptotic space depending on the implementation, and the safe statement is the pessimistic one. A tail-recursive accumulator loop is O(1) space only if the implementation guarantees it; the source-level analysis of “depth is n” holds until the elimination is confirmed by the language specification.

Output-sensitive bounds and in-place algorithms

Some algorithms have space costs that depend on the size of the answer rather than the size of the input, and the natural statement is a bound in both parameters. An algorithm that enumerates all maximal cliques of a graph, or all intersections among n line segments in the plane, may hold only a small working set while the output is large; the honest bound is something like O(k) where k is the output size, with the input-size term separate. Reporting such an algorithm as O(n) space is wrong in the direction that hides a real cost, and reporting it as O(k) alone hides the memory used to find the output.

Genuinely in-place algorithms sit at the other end. Heapsort runs in Θ(1) auxiliary space and Θ(n log n) time, and it is not stable. The simple stable merge needs a Θ(n) buffer. Stability with Θ(1) auxiliary space is also achievable, by merging through rotations instead of into a buffer, but the straightforward rotation-based merge costs Θ(n log n) moves per merge and therefore raises the whole sort to Θ(n log² n); recovering Θ(n log n) takes the more intricate block-merging techniques, which is why library sorts generally pay for the buffer.

A compact illustration of the auxiliary-space convention is a stable partition of an array, which holds one temporary regardless of how many elements it moves:

/* Stable partition of a[0..n) by pred in O(1) auxiliary space.
 * Each kept element is rotated left past the run of skipped elements, so both
 * classes keep their relative order; the cost is O(n^2) time in the worst case. */
static void stable_partition(int *a, int n, int (*pred)(int)) {
    int i = 0, j = 0;
    while (j < n) {
        if (pred(a[j])) {
            int value = a[j];
            for (int k = j; k > i; k--)  /* shift the kept element left */
                a[k] = a[k - 1];
            a[i] = value;
            i++;
        }
        j++;
    }
}

The auxiliary space is O(1), one int and two indices, and the time is Θ(n²) in the worst case, because each kept element shifts a run of skipped elements one place to the right. A merge-based stable partition is Θ(n log n) time and Θ(n) space. The trade is direct and honest: the space saving is paid for in time, and the class of the time bound is the price.

Space amortization and peak versus average

Memory that is freed and reused does not average the way time does, because the allocator cannot lend memory from the future. The relevant quantity is the peak, not the total. A routine that allocates a 2n buffer, copies into it, and frees the old n buffer has a peak of 3n even though its average occupancy over the operation is 2n, which is the memory side of the doubling policy analysed in amortized array growth. A routine that allocates and frees n separate O(1) blocks during its run has total allocation of Θ(n) bytes over time and a peak of O(1), and the two figures answer entirely different questions.

This is why the analysis of a heap-allocating routine differs from the analysis of a stack-allocating one. On the stack, the peak is the maximum depth and the sum over time is irrelevant. On the heap, the peak is the maximum of a running total that depends on deallocation timing, and the deallocation timing depends on the collector or on explicit frees. Garbage-collected runtimes add a further term, since the collector may need headroom proportional to the live set to run, and the amount is a property of the collector rather than of the algorithm.

The relationship between an amortized time bound and its memory shadow is the one examined in expected, amortized and average cost: credit accumulated by earlier operations has to be paid back in time, and the memory that backs it has to be accounted for separately. For a structure that is rebuilt periodically (a hash table, a dynamic array, a buffer), the peak memory during the rebuild is the old copy plus the new copy plus whatever the rebuild itself needs, and that peak, not the final size, is what has to fit.