Memory cost: space complexity
Measure how much extra memory an algorithm needs, spot hidden memory such as recursion and copies, and trade memory for speed on purpose.
OutOfMemoryException, a StackOverflowException, or simply an app that slows down because the garbage collector is busy. Space complexity uses the same Big-O language to describe how memory use grows with n.
What uses memory?
| Source | Example | Extra space |
|---|---|---|
int total, i; | O(1) | |
new int[n], new List<T>(items) | O(n) | |
.ToList(), .ToArray(), .OrderBy(...) | O(n) | |
s + x creates a new string | O(n) per step | |
O(depth) | ||
new bool[n, n] | O(n²) |
Recursion uses hidden memory
StackOverflowException, which cannot be caught.
// O(n) extra space: n + 1 frames alive at the deepest pointstatic long SumTo(int n) => n == 0 ? 0 : n + SumTo(n - 1); // O(1) extra space: same answer with a loopstatic long SumToLoop(int n){ long total = 0; for (int i = 1; i <= n; i++) total += i; return total;} Console.WriteLine(SumToLoop(1_000_000));// SumTo(1_000_000) would most likely crash with StackOverflowException500000500000
Trading memory for time
HashSet. Caching results (memoisation, next lesson) is the same deal. This trade-off is usually worth it, because memory is cheap and waiting is expensive, but it is a choice, not a free lunch.
| Approach | Time | Extra space |
|---|---|---|
O(n²) | O(1) | |
O(n log n) | O(1) to O(n) depending on the sort | |
HashSet | O(n) | O(n) |
In-place algorithms
How big is “n” in bytes?
| Item | Size in .NET (64-bit) | 1 million of them |
|---|---|---|
bool, byte | ||
int, float | ||
long, double | ||
Point3D struct of 3 doubles |
{ 1, 1, 2, 3, 3, 3, 7 } → k = 4 and the array starts 1, 2, 3, 7.
Show a hint
Show the solution
static int RemoveDuplicates(int[] a){ if (a.Length == 0) return 0; int write = 1; // a[0] is always kept for (int read = 1; read < a.Length; read++) { if (a[read] != a[write - 1]) // a new value a[write++] = a[read]; } return write;} int[] data = { 1, 1, 2, 3, 3, 3, 7 };int k = RemoveDuplicates(data);Console.WriteLine($"{k}: {string.Join(", ", data[..k])}");4: 1, 2, 3, 7
Remember
Space complexity describes how extra memory grows with n, in Big-O. New arrays, ToList()/ToArray(), string building and recursion depth all use memory.Fast algorithms often trade memory for time (HashSet, caching); make that choice consciously. In-place algorithms use O(1) extra space but change the input.