What is space complexity? How do you analyse the memory an algorithm uses in .NET, including auxiliary space, recursion depth, allocations and the GC, and how do you trade time for space?

1. Counting space correctly

Total memory = input + auxiliary. Interviews usually ask for auxiliary space; say which one you mean.

+---------------------------+
| input (n items)           |  not counted in auxiliary space
+---------------------------+
| extra arrays / sets       |  O(n) if proportional to input
| recursion stack frames    |  O(depth)
| fixed variables           |  O(1)
+---------------------------+

2. Recursion depth is space

Each call pushes a frame (return address, locals, saved registers), often 50–200 bytes or more in .NET:

Factorial(5)
  Factorial(4)
    Factorial(3)
      Factorial(2)
        Factorial(1)     <- 5 frames live at once: O(n) stack

The C# compiler and RyuJIT do not guarantee tail-call elimination, so do not rely on tail recursion to save stack. Convert deep recursion to a loop with an explicit Stack<T>, which lives on the heap.

3. Allocation is a cost even when Big O is fine

// O(n) space, n small allocations
var names = orders.Select(o => o.Name.ToUpperInvariant()).ToList();

// O(1) auxiliary: compare without allocating
int matches = 0;
foreach (var o in orders)
    if (o.Name.Equals("ACME", StringComparison.OrdinalIgnoreCase)) matches++;

Tools to reduce allocations:

4. Managed object overhead

On 64-bit .NET each object has a header and method table pointer (16 bytes) before its fields, and a reference costs 8 bytes. So List<int> with 1M items is about 4 MB, but List<object> with 1M boxed ints is about 8 MB of references plus 24 MB of boxes. Data layout changes the constant factor a lot even when Big O is the same.

5. Streaming: the most important space optimisation

ReadAllLines         Streaming
[ whole file ]       [ buffer ] -> process -> discard
[ all strings]       [ one line ]
[ all objects]       [ one row object ]
O(n) space           O(1) auxiliary space

In ASP.NET Core, returning IAsyncEnumerable<T> from an endpoint streams JSON, and EF Core's AsAsyncEnumerable() streams rows instead of buffering with ToListAsync().

6. Space-time trade-off catalogue

7. Try it yourself

// Compare peak memory of buffering vs streaming
using System.Diagnostics;
var path = Path.GetTempFileName();
await File.WriteAllLinesAsync(path, Enumerable.Range(0, 2_000_000).Select(i => $"{i},name{i},{i % 97}"));

long before = GC.GetTotalAllocatedBytes(true);
var all = File.ReadAllLines(path);
Console.WriteLine($"ReadAllLines allocated: {(GC.GetTotalAllocatedBytes(true) - before) / 1_048_576} MB");

before = GC.GetTotalAllocatedBytes(true);
long sum = 0;
foreach (var line in File.ReadLines(path)) sum += line.Length; // streaming
Console.WriteLine($"ReadLines allocated: {(GC.GetTotalAllocatedBytes(true) - before) / 1_048_576} MB (but never held at once)");
Console.WriteLine($"Peak working set: {Process.GetCurrentProcess().PeakWorkingSet64 / 1_048_576} MB");

Both allocate similar totals, but the streaming version only keeps one line alive at a time, so it can be collected in Gen 0 and peak memory stays flat.

// O(1) auxiliary space: in-place reverse
static void Reverse(int[] a)
{
    for (int i = 0, j = a.Length - 1; i < j; i++, j--)
        (a[i], a[j]) = (a[j], a[i]);
}

// O(n) auxiliary space: new array
static int[] ReversedCopy(int[] a) => a.Reverse().ToArray();

// Recursion: O(n) stack, can overflow for large n
static long SumRecursive(ReadOnlySpan<int> a) => a.IsEmpty ? 0 : a[0] + SumRecursive(a[1..]);

// Same result, O(1) auxiliary space
static long SumIterative(ReadOnlySpan<int> a) { long s = 0; foreach (var x in a) s += x; return s; }

// Reuse a pooled buffer instead of allocating per call
static async Task<long> CountBytesAsync(Stream s)
{
    var buffer = ArrayPool<byte>.Shared.Rent(81_920);
    try
    {
        long total = 0; int read;
        while ((read = await s.ReadAsync(buffer)) > 0) total += read;
        return total;
    }
    finally { ArrayPool<byte>.Shared.Return(buffer); }
}

// Stream rows from EF Core instead of ToListAsync()
await foreach (var order in db.Orders.AsNoTracking().AsAsyncEnumerable())
    await writer.WriteLineAsync($"{order.Id},{order.Total}");