Space Complexity: Auxiliary Memory, Recursion Stack and Allocations

Version note: The code in this post was built and run with .NET 10 (C# 14); measurements were taken with BenchmarkDotNet 0.15.8, tests with xUnit v3 4.0.2, and the container experiment with the mcr.microsoft.com/dotnet/runtime:10.0 image.

Guess First

Bookstore's order service produces a 1 GB log file every day: about 10.3 million lines. The support team wants a small tool to find a given customer's orders. Two developers write two versions; the only difference is how they read the file:

// Version A
var all = File.ReadAllLines(path);
foreach (var line in all) { /* ... */ }

// Version B
foreach (var line in File.ReadLines(path)) { /* ... */ }

Both have O(n) time complexity. What about memory? The tool will run in a container with a 512 MB memory limit. Which one stays within that limit and which one doesn't? And what does the one that doesn't do: throw an exception, get the container killed, or something else? Halfway through the post we'll run both on the same file in a real 512 MB container.

Total and Auxiliary Space

Space complexity describes how the memory an algorithm uses grows with n. There are two separate measures here, and mixing them up is very common. Total space counts all memory, including the input itself. Auxiliary space counts only the memory the algorithm allocates on top of the input. A method that reverses an array in place has O(n) total space (the array itself) and O(1) auxiliary space (two indexes and a temporary). When people say "this algorithm uses O(1) memory", they mean auxiliary space.

Algorithms with O(1) extra memory are called in-place. Insertion sort and heap sort are in-place. Classic merge sort isn't, because the merge needs a buffer of size n; the buffer parameter of MergeSort in the previous post is exactly that extra O(n).

Let's start with a simple comparison. We compute Fibonacci two ways. Memoization keeps previously computed values in a dictionary; the iterative version keeps only the last two values:

// Time O(n), space O(n): trades memory for avoiding repeated work
public static long MemoFibonacci(int n, Dictionary<int, long> memo)
{
    if (n < 2) return n;
    if (memo.TryGetValue(n, out var cached)) return cached;
    var value = MemoFibonacci(n - 1, memo) + MemoFibonacci(n - 2, memo);
    memo[n] = value;
    return value;
}

// Time O(n), space O(1): keeps only the last two values
public static long IterativeFibonacci(int n)
{
    long previous = 0, current = 1;
    if (n == 0) return 0;
    for (var i = 2; i <= n; i++)
    {
        (previous, current) = (current, previous + current);
    }
    return current;
}

memo      fib(90) = 2,880,067,194,370,816,120  entries = 89  allocated = 4,632 bytes
iterative fib(90) = 2,880,067,194,370,816,120  allocated = 0 bytes

Both find the same result in O(n) time. Memoization with an 89-entry dictionary and 4,632 bytes of allocations, the iterative version with zero allocations. But memoization has another hidden cost: because it's recursive, it also goes n deep on the call stack. That's the main topic of this post.

The Recursion Stack: Depth Is Memory

Every method call opens a frame on the call stack: the return address, parameters, local variables. If a recursive function goes d deep, then during the deepest call d frames sit on the stack at the same time. So the space complexity of recursion is at least O(depth). You lose that memory without seeing a single new in the code and without allocating any collection.

Think about Bookstore's category tree. Every category has a parent, and we want the depth of a category. Normally the tree is a few levels deep; but what happens if an import bug produces a 100,000-level chain?

public sealed class CategoryNode(string name, CategoryNode? parent = null)
{
    public string Name { get; } = name;
    public CategoryNode? Parent { get; } = parent;
}

// O(depth) stack: every level keeps a frame until the root is reached
public static int DepthRecursive(CategoryNode node) =>
    node.Parent is null ? 1 : 1 + DepthRecursive(node.Parent);

// O(1) extra space: one variable walks up the chain
public static int DepthIterative(CategoryNode node)
{
    var depth = 1;
    for (var current = node; current.Parent is not null; current = current.Parent)
    {
        depth++;
    }
    return depth;
}

How deep we can go is decided by the stack size. On macOS I read each thread's stack size with pthread_get_stacksize_np:

main thread          : 7.98 MB
new Thread()         : 1.51 MB
new Thread(.., 16 MB): 16.01 MB
thread pool          : 1.51 MB

The main thread uses the 8 MB the operating system gives it (ulimit -s 8176 KB). Threads .NET creates itself, including the thread pool, start with 1.5 MB on this machine. Because ASP.NET Core runs requests on the thread pool, the real limit for production code is the thread pool's, not the main thread's. These values vary with the operating system and runtime settings; don't assume them without measuring. Running the same 100,000-deep chain on two different threads:

$ dotnet Bookstore.Complexity.Demos.dll depth 100000
recursive depth = 100,000

$ dotnet Bookstore.Complexity.Demos.dll depth 100000 thread
Stack overflow.
   at Bookstore.Complexity.CategoryNode.get_Parent()
   at Bookstore.Complexity.SpaceExamples.DepthRecursive(Bookstore.Complexity.CategoryNode)
   at Bookstore.Complexity.SpaceExamples.DepthRecursive(Bookstore.Complexity.CategoryNode)
   ...
   at Post03+<>c__DisplayClass4_0.<Depth>b__0()
   at System.Threading.Thread+StartHelper.Callback(System.Object)
$ echo $?
134

Code that works on the main thread brings the process down the moment it moves to the thread pool. The output is 49,508 lines; so about 49,500 frames fit in the 1.5 MB stack, roughly 32 bytes per frame. Exit code 134 says the process was terminated with SIGABRT.

The important part: StackOverflowException can't be caught. The Microsoft docs say plainly that you can't catch it with try/catch and the process is terminated by default. No try block, global exception handler or middleware will save you; the whole process goes down, along with every other request in it. That's why recursion whose depth depends on the input, any depth the user or the data controls, is either written iteratively or guarded by an explicit depth limit. The call stack itself is covered in "Debugging in C#: Breakpoints, the Call Stack, Debug.Assert and Compiler Warnings" in the C# Fundamentals series, and techniques for turning recursion into iteration in the recursion post of the Algorithms and Data Structures series.

The iterative version walks a 1,000,000-level chain without trouble. An xUnit test verifies this:

[Fact]
public void IterativeDepth_HandlesChainsTooDeepForRecursion()
{
    var leaf = SpaceExamples.BuildChain(1_000_000);

    Assert.Equal(1_000_000, SpaceExamples.DepthIterative(leaf));
}

The stack cost of recursion depends on depth, not on the total number of calls. Merge sort is called n log n times, yet at most log₂ n frames are on the stack at once: 20 for 1,000,000 elements. Naive Fibonacci makes 2.7 million calls, yet for fib(30) there are at most 30 frames on the stack. The dangerous kind is recursion whose depth grows linearly with n: walking a linked list, a chain or an unbalanced tree recursively.

APIs That Produce Copies

The second hidden source of memory is methods that produce copies. ToList() and ToArray() allocate a new n-element collection every time they're called: O(n) extra memory. Substring allocates a new string and copies the characters. Split allocates both an array and a string for each part.

I wrote two parsers that read the price from log lines. One uses Split, the other slices whatever follows the last ; on a span:

// "978-0000000001;Title 1;Author 1;10.50" -> 10.50
// Split allocates a string[] and one string per field
public static decimal WithSplit(string line) =>
    decimal.Parse(line.Split(';')[3], System.Globalization.CultureInfo.InvariantCulture);

// Slicing a span allocates nothing
public static decimal WithSpan(string line)
{
    var span = line.AsSpan();
    var lastSeparator = span.LastIndexOf(';');
    return decimal.Parse(span[(lastSeparator + 1)..], provider: System.Globalization.CultureInfo.InvariantCulture);
}

| Method | Mean     | Ratio | Gen0   | Allocated |
|------- |---------:|------:|-------:|----------:|
| Split  | 53.29 ns |  1.00 | 0.0334 |     280 B |
| Span   | 23.57 ns |  0.44 |      - |         - |

The span version is more than twice as fast and allocates nothing; Split allocates 280 bytes per line. On a 10-million-line log that's 2.8 GB of allocations. ReadOnlySpan<char> is a window over existing memory; slicing only changes the start and length, O(1). The rules and limits of spans are in "Span<T> and Memory<T> in C#: Allocation-Free Parsing, stackalloc and ref struct Rules" in the Advanced C# series.

The Time-Space Trade-off

Deliberately trading memory for time is the oldest trick in algorithm design. Memoization stores results so it doesn't solve the same subproblem twice. A lookup table computes an expensive calculation in advance and writes it into a table. A precomputed index puts the data you'll query into a Dictionary or a sorted array ahead of time.

The order matching from the previous post is a typical example: we spent O(m) extra memory for m customers and brought O(n·m) time down to O(n+m). But there's an interesting detail. In that benchmark the dictionary version allocated less: 84.95 KB versus 140.68 KB at 1,000 records. The reason is that the naive version allocates a new closure and delegate for every order; because the lambda c => c.Id == order.CustomerId captures order, an object is created on every pass of the loop. The trade-off isn't always "more memory, less time"; sometimes both sides improve together.

The reverse works too. If memory is constrained you can sacrifice time: recompute every time, write results to disk and read them back, process the data piece by piece. That's exactly the topic of the next section.

Reading a 1 GB Log File: O(n) vs O(1) Memory

Back to the guessing section. I generated a 1 GB file with 10,288,949 lines and ran both versions under macOS's /usr/bin/time -l, which reports the process's peak resident memory (RSS, Resident Set Size):

public static void ReadLog(string path, string mode)
{
    var stopwatch = Stopwatch.StartNew();
    long errors = 0, lines = 0;
    if (mode == "all")
    {
        // The whole file in memory: O(n) memory
        var all = File.ReadAllLines(path);
        lines = all.Length;
        foreach (var line in all)
        {
            if (line.Contains("customerId=42 ")) errors++;
        }
    }
    else
    {
        // Streaming line by line: O(1) extra memory (as large as the longest line)
        foreach (var line in File.ReadLines(path))
        {
            lines++;
            if (line.Contains("customerId=42 ")) errors++;
        }
    }
    Console.WriteLine($"{mode,-6} lines={lines:N0} matches={errors:N0} time={stopwatch.ElapsedMilliseconds:N0} ms " +
                      $"totalAllocated={GC.GetTotalAllocatedBytes() / 1024 / 1024:N0} MB");
}

stream lines=10,288,949 matches=1,032 time=604 ms totalAllocated=2,275 MB
            54493184  maximum resident set size
all    lines=10,288,949 matches=1,032 time=2,128 ms totalAllocated=2,609 MB
          2841362432  maximum resident set size

With ReadLines the process peaked at 52 MB, with ReadAllLines at 2,710 MB. The 1 GB file took 2.7 GB in memory, because .NET strings are stored in the Unicode Transformation Format (UTF) encoding UTF-16, 2 bytes per character and every line also carries its own object header. The streaming version is also three and a half times faster: keeping 10 million strings alive means a load the GC (Garbage Collector) constantly has to move and scan.

Now the real question. I ran the same two commands in a container limited with --memory=512m:

$ docker run --rm --name bigowork-oom-stream --memory=512m -v "$B":/app:ro -v "$PWD/data":/data:ro \
    mcr.microsoft.com/dotnet/runtime:10.0 dotnet /app/Bookstore.Complexity.Demos.dll readlog /data/orders.log stream
stream lines=10,288,949 matches=1,032 time=1,167 ms totalAllocated=2,275 MB

$ docker run -d --name bigowork-oom-all --memory=512m -v "$B":/app:ro -v "$PWD/data":/data:ro \
    mcr.microsoft.com/dotnet/runtime:10.0 dotnet /app/Bookstore.Complexity.Demos.dll readlog /data/orders.log all
$ docker logs -t bigowork-oom-all
2026-11-08T09:22:53.541974424Z Out of memory.
$ docker stats --no-stream --format '{{.CPUPerc}} {{.MemUsage}}' bigowork-oom-all
100.65% 388.3MiB / 512MiB
$ docker stop -t 2 bigowork-oom-all
$ docker inspect -f 'exit={{.State.ExitCode}} oom={{.State.OOMKilled}}' bigowork-oom-all
exit=143 oom=false

$ docker run --rm --name bigowork-oom-catch --memory=512m ... readlogcatch /data/orders.log
OutOfMemoryException after 378 MB allocated; GC limit = 384 MB

The streaming version ran without trouble in the container too. The ReadAllLines version, however, neither exited cleanly with an exception message nor got the container OOMKilled. One second after starting it wrote only Out of memory. to stderr, then sat at 388 MiB with 100 percent CPU (Central Processing Unit) usage for nine minutes; I finally stopped the container myself (exit code 143, i.e. SIGTERM (the terminate signal); OOMKilled=false). Running the same code through the readlogcatch variant, which wraps ReadAllLines in a try/catch, made the picture clear: after 378 MB of allocations a managed OutOfMemoryException was thrown, and the limit the GC reported was 384 MB, i.e. 75 percent of 512 MB. Because .NET's GC reads the container limit and keeps the heap below it, the kernel didn't kill the process; the hang after the uncaught exception is the behavior I observed on this machine, and I didn't investigate its cause here. The lesson: a .NET process that hits its memory limit doesn't always die with a clean crash; without a health check and a memory alert you might not notice such a process for hours. The real fix isn't raising the limit but turning code that needs O(n) memory into O(1).

Allocations and GC Pressure

There's a striking number in the output above: the streaming version also allocated 2,275 MB in total. A new string is created for every line and becomes garbage on the next pass of the loop. Its space complexity is O(1), because only one line is alive in memory at a time. But total allocation is O(n).

The distinction matters. Space complexity answers "how much memory is alive at once"; it decides whether the process hits its memory limit. Total allocation decides how much work the GC does; it affects latency and CPU time. Short-lived allocations are collected cheaply in Gen0, but cheap doesn't mean free. Processing lines as spans over a PipeReader or a buffer instead of as strings brings these allocations close to zero too; measurement and technique are in "Performance in C#: Allocations, Structs and Measuring with BenchmarkDotNet" in the Advanced C# series.

In Production

"Memory is cheap" is true on a developer machine, not in a container. In Kubernetes, when a pod exceeds its memory limit, the kernel's OOM (Out Of Memory) killer kills the process and the pod ends up OOMKilled with exit code 137. .NET reads the container limit to avoid this: the GC's heap hard limit defaults to 75 percent of the container limit (Microsoft's GC configuration docs). The 384 MB limit the GC reported in the experiment above is exactly that.

A few rules reduce these surprises in production. Process anything whose size comes from outside, such as files, HTTP (Hypertext Transfer Protocol) bodies and database results, as a stream; for ReadAllLines, ReadAllText, ToListAsync() and ReadAsStringAsync() calls, ask "what if this data is 10 times larger tomorrow?" Don't let the input decide recursion depth; that's why JSON (JavaScript Object Notation) parsers have a max depth setting. And measure memory with peak RSS or a container metric, not with GC.GetTotalAllocatedBytes; they answer different questions.

Common Pitfalls

Treating recursion as free. Thinking space complexity is O(1) because there's no new in the code. Every level is a frame.

Trying to catch StackOverflowException. It can't be caught; the process goes down. The remedy is a depth limit or iterative code.

Testing on the main thread and running on the thread pool. A console demo passes with an 8 MB stack; the same code fails in ASP.NET Core with 1.5 MB.

Taking file size for memory size. A 1 GB UTF-8 file took 2.7 GB in memory.

Confusing peak memory with total allocations. The streaming version allocated 2.2 GB but never went above 52 MB at any moment.

Needless ToList(). Every ToList() added "just to be safe" in the middle of a LINQ (Language Integrated Query) chain means O(n) extra memory. Don't materialize a result you'll walk once; if you'll walk it several times, materialize it once.

A Small Experiment

★☆☆ Run DepthRecursive on a thread created with new Thread(..., maxStackSize: 16 * 1024 * 1024). Does a depth of 100,000 pass? Roughly how deep can you go?

★★☆ Run MemoFibonacci(90) on a 1.5 MB thread, then raise n to 100,000 (the result won't fit in a long; ignore the overflow and look only at the depth). At which n does it fail? How does the memory use of the iterative version change with n?

★★★ Write the log reader so it processes lines without turning them into strings (FileStream + a buffer + searching for "customerId=42 "u8 inside a ReadOnlySpan<byte>). Compare total allocations and time with the ReadLines version.

Up to this post we looked at the cost of each operation one at a time. But some operations are cheap most of the time and expensive once in a while: List<T>.Add is documented as "sometimes O(n)", yet everyone calls it O(1). In the next post we'll show why that's right using amortized analysis.