Quadratic Space On

Quadratic Space O(n²)

Time complexity gets all the attention, but the memory an algorithm reserves can fail you just as hard — a program that is fast but allocates too much simply crashes with OutOfMemory. Quadratic space, written O(n²), describes an algorithm whose peak extra memory grows in proportion to the square of the input size n. The mental picture is a grid: if your data has n items and you build a structure that holds one cell for every pair of items — an n-by-n table — you are using quadratic space. Line the items up along the top and down the side, and the box you fill is n rows by n columns.

Precise definition

An algorithm uses O(n²) space if there exist constants c and n₀ such that for all inputs of size n ≥ n₀, the additional memory it allocates is at most c·n². Big-O is an upper bound: it caps the growth rate and ignores constant factors and lower-order terms, so 3n² + 5n + 9 is still O(n²) — the n² term dominates as n grows.

Two clarifications that separate strong candidates from weak ones. First, space normally means auxiliary (extra) space — memory you allocate beyond the input itself; the input array is usually not counted. Second, the defining behaviour is how the requirement scales. Because the quantity is proportional to n², multiplying the input size by a factor k multiplies the memory by k² — not by k. This squaring is the single fact interviewers most want you to internalise.

Worked example: counting the cells

Consider building a full pairwise distance matrix for n points — dist[i][j] holds the distance between point i and point j. You allocate an n×n array of numbers.

• n = 1000: the matrix has 1000 × 1000 = 1,000,000 cells. At 8 bytes per number that is 8 MB. Comfortable.
• n = 2000 (input doubled, k = 2): 2000 × 2000 = 4,000,000 cells — 32 MB. Doubling the input gave 4× (k² = 2²) the memory, not 2×.
• n = 10,000 (10× the original, k = 10): 10,000 × 10,000 = 100,000,000 cells — 800 MB. Ten times the input is 100× (k² = 10²) the memory.

Watch the trap: the input grew 10×, but the memory grew 100×. Never carry the input factor straight through to the memory factor — always square it. This is exactly why a matrix that fits on a laptop at n = 10k needs roughly 80 GB at n = 100k and cannot be held in RAM at all.

Pitfalls and what an interviewer probes

• Squaring the wrong factor. Say "10× input → 10× memory" and you have missed the entire point. It is 100×. Interviewers plant this to see if you reason from n² or from a memorised phrase.
• Confusing time with space. Two nested loops that only keep a running counter are O(n²) time but O(1) space. Quadratic space requires you to actually store ~n² things. Always ask: what persists in memory at the peak?
• Forgetting the recursion stack. Space includes the call stack. Also, an algorithm can be sneaky: string edit-distance with a full DP table is O(n²) space, but the same answer needs only O(n) space if you keep just the previous row.
• Ignoring the constant, then hitting a wall. Big-O hides the per-cell size. An n×n grid of 8-byte doubles versus 4-byte ints differs 2× in real bytes — irrelevant to the class, decisive to whether it fits.
• “Just store half the matrix.” For a symmetric table (e.g. a distance matrix where dist[i][j] = dist[j][i]) you can keep only the upper triangle — n(n−1)/2 cells. That halves the bytes but the class is unchanged: n(n−1)/2 is still Θ(n²). Constant-factor savings never move you to a smaller class.

When it matters, and trade-offs vs neighbours

Quadratic space is common and often correct: dynamic-programming grids (edit distance, sequence alignment), dense graph adjacency matrices, all-pairs tables, and 2D memoisation caches. It is a deliberate time-for-space trade — a precomputed n×n lookup can turn repeated O(n) queries into O(1), which is a great deal when n is modest (hundreds to low thousands).

It sits sharply between its neighbours. O(n) space grows linearly — 10× input, 10× memory — and scales to billions of items. O(n²) grows by the square, so it is usually fine to n ≈ 10⁴ and hopeless past n ≈ 10⁵ (that is 10¹⁰ cells ≈ 80 GB). The next rung, O(n³), is dramatically worse still. The engineering instinct: reach for a quadratic table when n is bounded and small, but the moment inputs might grow large, look for a linear-space reformulation (streaming, rolling rows, sparse structures) before the k² blow-up makes the machine fall over.

Key takeaways

• O(n²) space stores an amount of extra memory proportional to n² — picture an n×n grid, one cell per pair of items.
• Scaling is the crux: multiply the input by k and memory multiplies by k² (2×→4×, 10×→100×) — never conflate the input factor with the memory factor.
• Quadratic space means you actually retain ~n² values; it is independent of time complexity and can often be cut to O(n) by keeping only the previous row/state.
• Practical for small, bounded n (tables, DP grids, dense graphs) as a time-for-space trade; switch to linear-space designs before n grows large.