Cairn
guides · cross-cutting lens, not tied to one category

↩ back to Guides

Space for Time

The idea: paying memory you don't strictly need

A structure never has to store more than the raw input it's built from — but several entries on this site deliberately do, precomputing extra tables purely to make a later query cheaper or more tightly bounded. This page asks the question none of the site's other cross-cutting lenses asks directly: how much extra memory does that actually cost, in real numbers, and does the speed it buys pay that back? Online vs. Offline asks whether the queries are known in advance; Memoization vs. Tabulation asks it only inside one dynamic-programming recurrence. Here the question is general: pick a structure that trades memory for speed, measure the real trade on both sides, not just the Big-O shape of each.

Sparse Table vs. Segment Tree: more memory for a bound Segment Tree can't promise

Sparse Table's own Complexity section already names the shape of the trade: O(n log n) space against Segment Tree's O(n), in exchange for O(1) queries a mutable tree can't offer at any space budget, since it has to leave room for update to invalidate exactly the nodes a change touches. Counting the real reference implementations' own stored values — Sparse Table's log₂n rows, each shorter than the last, against Segment Tree's one 2·size array — turns "more memory" into an actual number, and it isn't a fixed constant:

nSparse Table values storedSegment Tree values storedratio
1,0249,228 (9.0× n)2,048 (2.0× n)4.5×
131,0722,097,171 (16.0× n)262,144 (2.0× n)8.0×
1,048,57619,922,966 (19.0× n)2,097,152 (2.0× n)9.5×
16,777,216385,875,994 (23.0× n)33,554,432 (2.0× n)11.5×

(Sizes chosen as exact powers of two so Segment Tree's own array never pads past its tight 2n — off a power-of-two boundary its array can run to nearly 4n, per that page's own Complexity section, which would blur the comparison with Segment Tree's own internal waste rather than Sparse Table's.) The ratio keeps climbing because Sparse Table's row count grows with log₂n while Segment Tree's stays a flat 2× — by sixteen million keys, Sparse Table is storing over eleven times as many numbers for the same input. That memory isn't free in build time either: Sparse Table's own measured comparison found the break-even point — the query count needed before the faster O(1) lookups actually pay back the slower, larger build — lands at roughly 1.5×–4× the array's own size in queries, growing wider as n grows, not narrower. Both halves of this trade get more expensive at scale, not just one.

Bit Vector Rank/Select vs. a naive scan: real numbers, not just Big-O

Bit Vector Rank/Select's own reference implementation precomputes a block/superblock decomposition specifically so rank1(i) never has to scan — that page's own Space section already asserts the overhead is o(n) bits for the right choice of block size, but names no actual number. Instrumenting that exact shipped buildRankSelect function (unmodified) against a plain linear scan that counts set bits one at a time, at the same block/superblock sizing that page's own Space section names (block size b ≈ log₂(n)/2, superblock size S ≈ (log₂n)²) gives a real number, and a real trend:

nblock size, blocks/superblockextra words storedas % of nrank1 array reads: precomputed vs. naive scan
1,000b=5, 2088388.3%3 vs. 730
100,000b=8, 3541,18741.2%3 vs. 73,000
1,000,000b=10, 40318,88531.9%3 vs. 730,000
10,000,000b=12, 452,596,34626.0%3 vs. 7,300,000

Correctness checked first, not assumed: the precomputed rank1 matched an independent naive scan on every one of several hundred random query points at each size above, zero mismatches, before trusting any of these counts. rank1's own array-access count never moves — exactly 3 lookups (superRank, blockRankInSuper, one pattern-table row), at any n and any query position i — while a naive scan's cost grows with i directly, up to n at the array's far end. The overhead really is shrinking relative to n as the page's Space section claims (o(n), not a fixed fraction) — 88% of n at a thousand bits, down to 26% by ten million — but it's a real, nonzero memory bill the whole way, not a rounding error, and it shrinks slowly: cutting it in half again would take roughly another hundred-fold increase in n at this growth rate.

Try it

Pick a size and this recomputes the exact same closed-form word count as the table above — 2b·(b+1) + b·2b-1 for the shared pattern tables plus 3·⌈n/b⌉ for the per-block arrays plus ⌈⌈n/b⌉/(S/b)⌉+1 for superRank — verified above to match the real shipped structure's own counts exactly, not an estimate.

Where else this shows up

Pitfalls

The extra memory has to be built before it pays anything back, and that build has a real cost too — not just a one-time footprint. Sparse Table's own measured comparison above shows the build gap widening with n exactly as the query-time saving stays roughly fixed in nanoseconds — "spend memory, get speed" is really "spend memory and build time, get speed back gradually, one query at a time." A workload that builds the structure once and queries it only a handful of times never clears that bar, no matter how large the per-query saving looks in isolation.

"Smaller than a fixed multiple of n" and "small" are different claims. Bit Vector Rank/Select's o(n) bound is real and measured above, but at a thousand bits the overhead is still 88% of the raw data it indexes — nowhere near negligible at that size. The asymptotic claim only becomes a practical win once n is large enough for the shrinking trend to have actually shrunk; reading an asymptotic space bound as "cheap at any size" skips exactly the part a real measurement would catch.

The right block/superblock size isn't a free constant choice. Bit Vector Rank/Select's own Complexity section is explicit that the o(n) bound "only holds for the right choice of block size b and superblock size S, not any fixed constant" — the table above recomputes b and S at every n for exactly that reason, rather than reusing one pair of numbers across every row, which would have quietly misrepresented the trend at the extremes.