Space Complexity: Call Stacks, Tail Recursion & Auxiliary Heap

Input Space vs Auxiliary Space & Stack Frame Reuse

Let an algorithm accept an input of size $N$. Its memory footprint is partitioned into three distinct regions:

• Input Space: The memory occupied by the input parameters themselves. An in-place algorithm (strictly defined as $O(1)$ auxiliary space, or loosely in sorting as $O(\log N)$ auxiliary stack space) mutates the input buffer directly without allocating a proportional copy.
• Auxiliary Call-Stack Space: On x86-64 System V ABI, every call instruction pushes an 8-byte return instruction pointer (%rip), saves the caller's frame pointer (%rbp) and any modified callee-saved registers (%rbx, %r12–%r15), allocates local variables, and pads the stack pointer (%rsp) to a 16-byte alignment boundary. Consequently, even a function with a single int parameter consumes 32 to 64 bytes per stack frame.
• Auxiliary Heap Space: Dynamic allocations (malloc, new, std::vector) reside in the process heap. Every heap allocation carries an 8–16 byte allocator metadata header (size_t chunk size + flags in jemalloc/ptmalloc) and rounds up to size-class bins (16B, 32B, 48B, 64B).

Visualizing x86-64 Stack Frame Layout & Tail-Call Frame Overwrite

The diagram below compares standard non-tail recursion (which grows downward in memory by 48 bytes per call toward the guard page) against Tail-Call Elimination (which mutates arguments inside the existing frame and jumps to the function prologue).

Production Pattern: Sedgewick's $O(\log N)$-Stack Quicksort

The C++20 implementation below demonstrates how to guarantee $O(\log N)$ worst-case stack space in Quicksort by recursing strictly on the smaller partition and converting the larger partition into an iterative while loop.

// C++20: Sedgewick's Smaller-Half Tail-Eliminated Quicksort (Strict O(log N) Auxiliary Stack)
#include <algorithm>
#include <cstddef>
#include <span>

ptrdiff_t hoarePartition(std::span<int64_t> a, ptrdiff_t lo, ptrdiff_t hi) noexcept {
    int64_t pivot = a[lo + (hi - lo) / 2];
    ptrdiff_t i = lo - 1;
    ptrdiff_t j = hi + 1;
    while (true) {
        do { ++i; } while (a[i] < pivot);
        do { --j; } while (a[j] > pivot);
        if (i >= j) return j;
        std::swap(a[i], a[j]);
    }
}

// Guaranteed <= log2(N) stack frames even on 100% adversarial inputs!
void safeQuicksort(std::span<int64_t> a, ptrdiff_t lo, ptrdiff_t hi) noexcept {
    while (lo < hi) {
        ptrdiff_t p = hoarePartition(a, lo, hi);
        // Recurse ONLY on the smaller half (at most half the current range);
        // handle the larger half via the enclosing while-loop (Tail-Call Elimination).
        if (p - lo < hi - (p + 1)) {
            safeQuicksort(a, lo, p);
            lo = p + 1; // Tail-call eliminated!
        } else {
            safeQuicksort(a, p + 1, hi);
            hi = p;     // Tail-call eliminated!
        }
    }
}