van Emde Boas Trees

By the end of this lesson you will be able to explain why comparison-based priority queues can never beat Ω(lg n) per operation, but a structure built for a fixed integer universe {0, …, u−1} can search, insert and delete in only O(lg lg u) time — trace the direct-address bit vector, its binary tree of bits, the proto-vEB structure, and the full van Emde Boas tree step by step, and implement every one of vebMember, SUCCESSOR, PREDECESSOR, INSERT and DELETE in working Dart, verified against a sorted-set reference.

0. Why bother? Beating the comparison-sort lower bound

Imagine a parcel depot where parcels are placed purely by comparing labels against each other — every lookup is "is this label bigger or smaller than that one?". No matter how cleverly you organize such a depot, some questions need about lg n comparisons in the worst case, the same reason binary search needs lg n guesses. But now imagine every parcel carries a locker number from 0 to u−1 and the shelves are built to exploit that numbering directly: a depot that shelves strictly by locker number can jump straight to shelf ⌊number / shelf-size⌋. Numbers let you do arithmetic tricks that pure comparisons never allow.

The comparison-based priority queues you have met (binary heaps, red-black trees, Fibonacci heaps) and comparison sorting in general share a hard floor: any comparison-based priority queue must take Ω(lg n) time for at least one of INSERT or extractMin. Why? If both ran faster, you could sort n numbers in o(n lg n) time by doing n INSERTs followed by n extractMin calls — contradicting the Ω(n lg n) comparison-sorting lower bound, which is proved via the decision-tree argument.

Dart: the reduction as code — n INSERTs, then n extractMin calls sort n distinct keys. With comparisons only this loop costs Ω(n lg n); with a vEB tree as the queue it is O(n lg lg u) because the keys are used as addresses (tested in verify/c20.dart).

Input size → what’s feasible: n = 10⁶ keys in u = 2²⁰ → a balanced BST needs about lg n = 20 comparisons per operation (2·10⁷ steps in total), a vEB tree about 5 levels (5·10⁶), but the dense vEB tree must pre-build 1,421,676 nodes; u = 2³² → the dense tree would need 6.0·10⁹ nodes (impossible), so use a BST or the reduced-space tree of Section 8.

But that lower bound only binds algorithms that treat keys as opaque, comparable blobs. The moment you're told keys are distinct integers drawn from a known, fixed range {0, 1, …, u−1} (exactly the assumption behind counting sort), you can use the key's own bit pattern as an address, the same trick this lesson pushes to its logical extreme. A van Emde Boas tree (vEB tree) supports MEMBER, INSERT, DELETE, MINIMUM, MAXIMUM, SUCCESSOR and PREDECESSOR — the full "dynamic set" toolkit — in O(lg lg u) worst-case time each. For u = 2^32, lg lg u = 5: a handful of steps versus the lg n a balanced tree would need.

A vEB tree is not a drop-in replacement for a comparison-based structure: it needs to know the universe size u up front, its keys must be non-negative integers (or something that maps to them), no two elements may share a key (duplicates need a side counter or list per key), and — as you will see in Section 1 — its space cost is O(u), not O(n), unless you use the reduced-space variant from Section 8. It trades those restrictions for the same O(lg lg u) bound on every operation, including the ones like MINIMUM/MAXIMUM that a plain balanced BST already does in O(1)/O(lg n), and SUCCESSOR/PREDECESSOR which a balanced BST needs O(lg n) for.

Comparison-based structures are stuck at Ω(lg n) per operation because of an information-theoretic argument over orderings. A vEB tree sidesteps that argument entirely by exploiting a known, bounded integer universe, reaching O(lg lg u) — this lesson builds up to that structure in three stages: a bit vector, a proto-vEB structure, then the real thing.

1. Preliminary approaches

Think of a school with exactly 16 possible locker numbers, 0 through 15. The dumbest possible "is locker i occupied?" system is a wall of 16 lightbulbs, one per locker, lit when occupied — instant to check ONE locker, but to find the FIRST occupied locker you might have to look at all 16 bulbs. We build up three fixes to that, each one trading a little extra structure for a lot less scanning, before finally reaching the real van Emde Boas tree.

Direct-address bit vector. A single array A[0..u-1] of bits, A[x] = 1 iff x is in the set. INSERT/DELETE/MEMBER are all Θ(1) — one array access. But MINIMUM/MAXIMUM/SUCCESSOR/PREDECESSOR must scan, worst case Θ(u).

Dart (steps counts array reads; tested in verify/c20.dart):

Input size → what’s feasible: u ≤ 10⁶ → a MINIMUM/SUCCESSOR scan is ≤ 10⁶ reads, fine for a few queries; u = 2¹⁶ with 10⁶ queries → up to 6.5·10¹⁰ reads, far too slow → use a tree.

Binary tree of bits over that same vector: give every bit a parent whose value is the OR of its two children, all the way up to a single root — a segment tree recording, at every level, "does ANY leaf in my range have a member?" Height is lg u. MINIMUM follows the leftmost 1-path from the root down to a leaf; SUCCESSOR walks up until it can turn right into an unexplored subtree with a 1, then down the leftmost 1-path of that subtree. Every operation becomes O(lg u) — actually better than a red-black tree for MEMBER (which is O(1) here vs. a BST's O(lg n)), but no faster than a balanced BST for the rest.

Dart (level 0 holds the u leaves, the last level is the root; pos >> l is the ancestor of leaf pos at level l):

Input size → what’s feasible: u = 2¹⁶ → every operation is ≤ 16 steps (2u = 131,071 cells), 10⁶ queries ≈ 1.6·10⁷ steps; u = 2³² → still 32 steps but 2³³ = 8.6·10⁹ cells, so memory is the limit.

A tree of degree √u, height 2. Split the universe into √u clusters of √u elements each, plus a √u-bit summary (one bit per cluster, OR of that cluster). INSERT is O(1) (set one bit in the cluster, one in the summary). MIN/MAX/SUCCESSOR/PREDECESSOR/DELETE cost O(√u) — worse asymptotically than the binary-tree-of-bits approach for those specific operations, but the KEY idea this seeds — shrinking the universe by a square root, recursively — is exactly the seed the rest of this lesson grows into a genuine O(lg lg u) structure.

Dart, plus a step counter for the worst MINIMUM (the only member is u−1): u = 16 → 16 / 4 / 8 steps, u = 256 → 256 / 8 / 32, u = 65536 → 65536 / 16 / 512 (bit vector / binary tree / √u tree), all asserted in verify/c20.dart:

Input size → what’s feasible: u = 2¹⁶ → MINIMUM/SUCCESSOR ≤ 2√u = 512 steps (5·10⁸ for 10⁶ queries, borderline), INSERT stays O(1).

It's tempting to think "smaller cluster size = always better." A tree of degree u^(1/k) for larger k has MORE levels (height k), and each level still costs work proportional to its own size — there is a genuine trade-off between fan-out and height that only gets resolved by recursing the SAME idea at every level, all the way down, which is precisely what Section 2 does next.

Three preliminary structures, three trade-offs: bit vector (O(1) member, O(u) everything else), binary tree of bits (O(lg u) everything, O(1) member), √u-degree tree (O(1) insert, O(√u) everything else). None reach O(lg lg u) — that needs genuine recursion, applied at every level, which is Section 2's proto-vEB structure.

2. The proto-vEB structure

Instead of one flat vector or a fixed two-level tree, shrink the universe by a square root and then repeat the exact same trick inside each piece, recursively, until the pieces are so small (size 2) that there's nothing left to shrink. It's like a filing system where a giant warehouse is split into aisles, each aisle is split into shelves, each shelf into bins, each bin into slots — and every one of those containers is organized by the identical rule, all the way down. high(x) = ⌊x / √u⌋ picks WHICH aisle/shelf/bin/slot; low(x) = x mod √u picks the position WITHIN it; index(x, y) = x·√u + y glues the two back into the original address.

A proto-vEB(u) structure: if u = 2, it is just a 2-bit array A[0..1] (the base case). Otherwise it has a summary pointer to one proto-vEB(√u) structure (one bit per cluster, recording "is this cluster nonempty?"), and a cluster array of √u pointers, each to its own proto-vEB(√u) structure. Element x lives at position low(x) inside cluster[high(x)]. For u = 16: √16 = 4, so there are 4 clusters of size 4, plus a summary of size 4 — and since 4 itself is bigger than the base case, both the summary and every cluster recurse one more level down to size-2 leaves. (Section 3 will generalize to universes where lg u is odd by splitting √u into an upper root ↑√u and a lower root ↓√u; whenever lg u is even, as here, both simply equal √u.)

The recurrence that motivates this whole chapter: solving T(u) = T(√u) + O(1) by substituting m = lg u gives S(m) = S(m/2) + O(1), which the master method (case 2) solves as S(m) = O(lg m), i.e. T(u) = O(lg lg u). As you will see below, protoMember actually achieves exactly this recurrence — but the other three operations make MORE than one recursive call per level, and that single design flaw is what proto-vEB fails to fix (motivating the min/max fields added in Section 3).

Dart: the three recurrences as code, with m = lg u (a power of two here): T(m) = T(m/2) + 1 gives lg m + 1; T(m) = 2T(m/2) + 1 gives 2m − 1; T(m) = 2T(m/2) + m gives m(lg m + 1). All three closed forms are asserted for m = 1, 2, 4, …, 64:

protoMember(v, x)

Checks whether x is present by recursing into exactly the one cluster that could possibly contain it — one recursive call per level, achieving the target recurrence.

Input size → what’s feasible: u = 16 → 3 invocations; u = 2¹⁶ → 5; even u = 2³² → only 6 — but the structure holds Θ(u) nodes, so u ≤ 2¹⁶ (92,007 nodes) is the practical cap.

Dart (keys are plain integers in [0, u); null is NIL; _high/_low/_index are the high/low/index helpers):

In Dart (x is a key value in [0, u), not an array position): bool member(int x) { if (u == 2) return bits[x]; return cluster[high(x)].member(low(x)); } — see ProtoVEB.member in verify/c20.dart, tested against brute-force set membership on 30 random subsets of a 16-element universe.

protoMinimum(v)

Finds the smallest member by asking the summary which cluster is smallest-indexed-and-nonempty, THEN asking that cluster for its own minimum — two recursive calls per level.

Input size → what’s feasible: u = 2¹⁶ → 2·lg u − 1 = 31 invocations; u = 2³² → 63, already worse than the bit tree’s lg u = 32 steps.

Dart (keys are plain integers in [0, u); null is NIL; _high/_low/_index are the high/low/index helpers):

Two recursive calls per level means the call tree branches like a full binary tree of depth lg lg u (since each level's own universe again halves in log-size) — total calls grow like 2^{lg lg u} = lg u, giving T(u) = 2T(√u) + O(1) = Θ(lg u) by the master method's case 1. That is no better than the O(lg u) binary-tree-of-bits from Section 1, even though proto-vEB looks more sophisticated!

protoSuccessor(v, x)

Worst case makes up to three calls per level: search x's own cluster (SUCCESSOR), then the summary for the next nonempty cluster (SUCCESSOR), then that cluster's own MINIMUM (itself Θ(lg u)) — giving T(u) = 2T(√u) + Θ(lg u), which works out to Θ(lg u · lg lg u), the worst of the four proto-vEB operations.

Input size → what’s feasible: u = 2¹⁶ → up to 57 invocations (measured, Θ(lg u · lg lg u)); the vEB version needs at most 5.

Dart (keys are plain integers in [0, u); null is NIL; _high/_low/_index are the high/low/index helpers):

protoInsert(v, x)

Always makes exactly two unconditional recursive calls per level (insert into the cluster, AND insert into the summary, every single time — there is no way to skip the summary insert, since proto-vEB has no O(1) way to check "is this cluster already nonempty?"). This costs Θ(lg u), the same doubling problem as MINIMUM.

Input size → what’s feasible: u = 2¹⁶ → exactly 31 invocations per INSERT, always; n = 10⁴ inserts → 3.1·10⁵ calls fine, u = 2²⁰ → 39 per insert.

Dart (keys are plain integers in [0, u); null is NIL; _high/_low/_index are the high/low/index helpers):

protoDelete is deliberately not built here: the summary bit for a cluster can't simply be reset to 0 without first checking whether the cluster still has OTHER members, which needs either a linear scan of the cluster or an extra "count" attribute per node — exactly the kind of record-keeping the real vEB tree's min/max fields will make free.

Proto-vEB shows the recursive idea works for MEMBER (one call/level → O(lg lg u)) but fails for MINIMUM (2 calls → Θ(lg u)), SUCCESSOR (up to 3 calls, one of them itself Θ(lg u) → Θ(lg u · lg lg u)) and INSERT (2 unconditional calls → Θ(lg u)). The fix, coming next: store min and max directly on every node, so most of those "extra" calls become O(1) field reads instead.

3. The van Emde Boas tree — MINIMUM, MAXIMUM, MEMBER

The real vEB(u) tree takes the proto-vEB shape and adds two extra name-tags to every node: min and max. Think of a company org chart where every department, no matter how deep, wears a big sticker on its door reading "our most junior member is ___, our most senior is ___" — you never have to walk inside to find those two facts. There's one deliberate twist: the person listed as min is NOT also filed inside any of the department's own sub-teams — they exist ONLY as the sticker, nowhere else. That twist is what makes INSERT/DELETE/EMPTY-checks all O(1) at the point they're needed, and it is also the source of a subtle extra case in PREDECESSOR (Section 4).

To generalize beyond u = 2^{2^k}, we redefine the split using two square roots, written with an arrow above the radical. The upper square root ↑√u = 2^{⌈(lg u)/2⌉} (round the exponent UP) is the number of clusters, and the lower square root ↓√u = 2^{⌊(lg u)/2⌋} (round the exponent DOWN) is the size of each cluster. So high(x) = ⌊x / ↓√u⌋, low(x) = x mod ↓√u, index(x,y) = x·↓√u + y, and always ↑√u · ↓√u = u. For any power of two u this keeps the recursion well-defined: when lg u is even both roots equal √u (for u=16 both are 4, matching Section 2 exactly); when lg u is odd, ↑√u is twice ↓√u (for u=32: ↑√u = 8 clusters of size ↓√u = 4). A vEB(2) node has NO array at all — it is described entirely by min/max (empty: both NIL; one element: both equal that element; two elements: min=0, max=1). The explorer below shows the arithmetic on real bits.

Dart (the high/low/index helpers; upperSqrt is ↑√u and lowerSqrtOf is ↓√u; tested in verify/c20.dart):

The universal recurrence this lesson has been building toward: T(u) ≤ T(↑√u) + O(1). Substituting m = lg u: T(2^m) ≤ T(2^{⌈m/2⌉}) + O(1); since ⌈m/2⌉ ≤ 2m/3 for m ≥ 2, this becomes S(m) ≤ S(2m/3) + O(1), and the master method (case 2, since log_{3/2} 1 = 0) gives S(m) = O(lg m), i.e. T(u) = O(lg lg u). Every operation in this section and the next satisfies this exact recurrence by making at most one true recursive call per level.

Dart: the recurrence counted directly on u (tVeb), the inequality ⌈m/2⌉ ≤ 2m/3 behind the substitution (halvingBound), and the identity ↑√u · ↓√u = u with index(high(x), low(x)) = x (sqrtIdentity), asserted for every u = 2¹ … 2⁴⁰ (lg u ≤ 62 for tVeb):

vebMinimum(v) & vebMaximum(v)

Both are one-line field reads — O(1), no recursion at all, the first payoff of storing min/max directly.

Input size → what’s feasible: any u ≤ 2⁶² → one field read, O(1); 10⁸ calls ≈ 10⁸ steps.

Dart (keys are plain integers in [0, u); null is NIL; _high/_low/_index are the high/low/index helpers):

vebMaximum(v)

The mirror image, return v.max, O(1). Unlike v.min, the max is also stored inside the cluster that holds it (unless max = min).

Input size → what’s feasible: any u ≤ 2⁶² → one field read, O(1).

Dart (keys are plain integers in [0, u); null is NIL; _high/_low/_index are the high/low/index helpers):

vebMember(v, x)

Checks the min/max shortcut FIRST (O(1)); only if that misses AND the node isn't already a base case does it make its one recursive call.

Input size → what’s feasible: u = 2¹⁶ → at most 5 invocations (measured worst case 5), so 10⁷ queries ≈ 5·10⁷ invocations; the dense tree itself is the cap (92,007 nodes).

Dart (keys are plain integers in [0, u); null is NIL; _high/_low/_index are the high/low/index helpers):

Dart (keys are plain integers, so only the recursive structure matters): see VEBTree.member in verify/c20.dart —

bool member(int x) { if (x == min || x == max) return true; if (u == 2) return false; return cluster[high(x)].member(low(x)); }

— tested against a SplayTreeSet<int> reference over hundreds of randomized operations at u = 16, 256 and 65536.

A subtle but critical consequence of "min is never stored in any cluster": vebMember would give the WRONG answer for x == v.min if line 1 didn't check it explicitly first — recursing straight into cluster[high(x)] would never find it, because it genuinely isn't there. Every operation in this lesson that touches a cluster has to remember this exception.

Storing min/max on every node turns MINIMUM, MAXIMUM and the "is this cluster empty?" check into O(1) field reads, and lets MEMBER short-circuit before ever recursing. The one thing to always remember: v.min is a label on the node itself, never a resident of any child cluster.

4. vebSuccessor & PREDECESSOR

Looking for the next-bigger name in a department: first check the ONE sticker you already have for free — "is x smaller than our most junior member? then THEY are the answer, instantly." Otherwise, peek at the department x already belongs to: does IT already have someone bigger than x (its own max sticker tells you in O(1))? If so, descend into just that one department. If not, ask the head office (the summary) which OTHER department comes next, then read THAT department's own min sticker — again O(1), no need to descend a second time.

vebSuccessor(v, x)

Exactly one true recursive call happens per level — either into x's own cluster (if that cluster's max says there's room), or into the summary (to find the next cluster) — never both, and never the expensive MINIMUM-of-everything the proto-vEB version needed.

Input size → what’s feasible: u = 2¹⁶ → at most 5 invocations per SUCCESSOR (measured 5) versus 57 for proto-vEB; 10⁶ queries ≈ 5·10⁶ steps.

Dart (keys are plain integers in [0, u); null is NIL; _high/_low/_index are the high/low/index helpers):

Dart: VEBTree.successor in verify/c20.dart is a direct translation — maxLow/offset reads from vebMaximum/MINIMUM are plain field accesses (t.max, t.min), never method calls that themselves recurse, which is exactly why they don't add to the recursion depth.

vebPredecessor(v, x)

Symmetric to SUCCESSOR, with one genuinely extra case: if the summary search for an earlier nonempty cluster comes back empty, the predecessor might STILL be v.min itself — because, as Section 3's pitfall said, the minimum is invisible to every cluster and to the summary search alike.

Input size → what’s feasible: u = 2¹⁶ → at most 5 invocations per PREDECESSOR (measured 5); 10⁶ queries ≈ 5·10⁶ steps.

Dart (keys are plain integers in [0, u); null is NIL; _high/_low/_index are the high/low/index helpers):

Finding the successor or predecessor of x does not depend on x being in the set (the same is true in a binary search tree). The pseudocode here has that property — it never assumes x is a member — and the custom-input players above let you verify it directly: try a query key that was never inserted.

SUCCESSOR/PREDECESSOR each make at most ONE genuine recursive call per level (matching T(u) ≤ T(↑√u) + O(1) ⇒ O(lg lg u)), backed by O(1) field reads of neighboring MIN/MAX. PREDECESSOR needs one extra fallback case precisely because v.min lives only on its own node's sticker, never inside a child.

5. vebInsert

Hiring into an empty department is trivial: the new hire becomes both the junior and senior sticker, done. Hiring into a non-empty department is more interesting: if the newcomer is more junior than the current "most junior" sticker, THEY take over that sticker, and the person who used to hold it now has to actually go find a desk somewhere inside the department (because, remember, the min sticker-holder never has an actual desk in any sub-team). Then, whoever the "actual new desk-seeker" is, they go to the correct sub-team; if that sub-team was completely empty, seating them is instant (they become ITS min and max sticker) and the head office simply notes "this sub-team is no longer empty" — otherwise, they recurse into that one sub-team.

vebEmptyInsert(v, x)

The two-line helper both the empty-tree case of INSERT and the "seat someone as a cluster's very first member" case rely on: just set both stickers to the new value, O(1), no recursion.

Input size → what’s feasible: O(1) for every u: two field writes, no recursion.

Dart (keys are plain integers in [0, u); null is NIL; _high/_low/_index are the high/low/index helpers):

vebInsert(v, x)

Makes at most one true recursive call per level: EITHER into the summary (only when the target cluster was empty, paired with an O(1) vebEmptyInsert into that cluster) OR into the target cluster directly (when it already had members) — never both, matching T(u) ≤ T(↑√u) + O(1) exactly like SUCCESSOR did.

Input size → what’s feasible: u = 2¹⁶ → at most 5 invocations per INSERT (measured 5); building n = 10⁵ keys ≈ 5·10⁵ calls.

Dart (keys are plain integers in [0, u); null is NIL; _high/_low/_index are the high/low/index helpers):

vebInsert assumes x is NOT already present. Violating it corrupts the structure: the tests in verify/c20.dart insert 2 twice, which stores a second copy of the minimum inside a cluster, and after one DELETE(2) the key is still reported as a member. Check MEMBER first if duplicates are possible, as the verify harness does (if (!veb.member(x)) veb.insert(x)).

Dart (keys are integers, not positions): VEBTree.insert in verify/c20.dart mirrors the pseudocode almost line-for-line, including the min/max swap (final tmp = min!; min = x; x = tmp;) and the empty-cluster fast path.

INSERT: empty tree → O(1) vebEmptyInsert. Otherwise, possibly swap in a new min (the old min must then be re-homed), then either seed a freshly-nonempty cluster in O(1) plus one summary INSERT, or recurse into an already-populated cluster — never both. Exactly one true recursive call per level.

6. vebDelete

Firing your ONLY employee closes the department entirely — both stickers go blank. Firing someone who happens to be the CURRENT "most junior" sticker-holder is trickier: since that sticker-holder never actually had a desk, you first have to find whoever currently has the smallest actual desk somewhere inside (the head office already knows which sub-team has it), promote THEM to the sticker, and then it's really THEIR old desk that gets vacated. Either way, you then remove the vacated desk from its sub-team; if that empties the sub-team completely, you also tell the head office "this sub-team is now empty too" — and, only in that specific case, you might need to recompute who the new "most senior" sticker-holder is.

vebDelete looks like it might make two independent recursive calls (into a cluster, AND into the summary) — but the key insight is that these two calls are mutually exclusive in effect: the summary deletion only fires when the cluster-level deletion just emptied that entire cluster, and in THAT specific situation the cluster-level deletion was the O(1) singleton case (lines 1–4), so only one call is ever expensive. The worst-case analysis (not amortized) nets out to the same recurrence T(u) ≤ T(↑√u) + O(1) → O(lg lg u).

Input size → what’s feasible: u = 2¹⁶ → at most 9 invocations per DELETE (measured; ≤ 2 per level: one cheap singleton call plus one recursive call); 10⁶ deletes ≈ 9·10⁶ steps.

Dart (keys are plain integers in [0, u); null is NIL; _high/_low/_index are the high/low/index helpers):

Deleting a key that ISN'T present (violating its precondition) can corrupt min/max record-keeping — e.g. line 1's "v.min==v.max" singleton check would incorrectly empty a node that actually still has other members, if x was never really there in the first place. Always MEMBER-check before DELETE if you're not certain, exactly like verify/c20.dart's harness (if (veb.member(x)) veb.delete(x)).

Dart: VEBTree.delete in verify/c20.dart. The subtlest line is reassigning x itself mid-procedure (line 11 of the pseudocode) when deleting the minimum — the Dart translation reassigns the local parameter x the same way, which is exactly why Dart's parameters need to be non-final here (unlike almost every other lesson on this site, which prefers final wherever possible).

DELETE: singleton → empty the node, O(1). Deleting the min promotes a replacement from the first nonempty cluster (found via the summary's own O(1) min field) before doing the real per-cluster delete. The cluster-delete and summary-delete recursive calls only BOTH fire when the cluster just became empty — never independently — keeping the total to T(u) ≤ T(↑√u) + O(1).

7. Why it's O(lg lg u): the recurrence, visually

Each level of vEB recursion doesn't merely shrink the universe a little — it takes its SQUARE ROOT. Going from a universe of 4 billion down to "small enough to brute-force" by halving each time (u, u/2, u/4, …) would take 32 steps. Taking a square root each time (u, √u, √√u, …) reaches the same destination in only 5 steps — because repeatedly taking a square root is the same as repeatedly HALVING the EXPONENT of 2, and halving something 32 times is lg 32 = 5 steps.

Formally: let m = lg u. One vEB recursive call shrinks u to roughly √u, which means it shrinks m to roughly m/2. So the number of levels before u bottoms out at the base case (u=2, i.e. m=1) is exactly the number of times you can halve m before reaching 1 — that's lg m = lg lg u. Since every operation in Sections 3–6 does O(1) work per level (plus at most one recursive call), the total cost is O(1) × (number of levels) = O(lg lg u).

Dart: levels(lgU) counts how many times m = lg u can be replaced by ⌈m/2⌉ before it reaches 1 (that is ⌈lg m⌉ = ⌈lg lg u⌉); ceilLog2 gives the balanced-BST comparison. Asserted: u = 2³² → 5, u = 2⁶⁴ → 6, n = 10⁹ → 30:

Now measure it instead of trusting the algebra. The players below run real instrumented copies of the procedures in your browser, count every invocation (the first call plus each recursive call) and compare with lg lg u. The custom player lets you pick your own u.

For concrete intuition: u = 2^32 (a 32-bit universe, 4 billion keys) gives lg lg u = lg 32 = 5. Even u = 2^64 only gives lg lg u = lg 64 = 6. Compare a balanced BST on n = 10^9 elements, needing lg n ≈ 30 comparisons — the vEB tree's advantage widens dramatically for large, dense integer universes, which is exactly the setting the lesson opened with (Section 0).

vEB recursion shrinks the universe by a SQUARE ROOT at every level, which is the same as halving lg u at every level — so the recursion bottoms out after only lg(lg u) = lg lg u levels, and O(1) work per level gives the whole O(lg lg u) bound.

8. Going further: reduced-space vEB, y-fast tries

A plain vEB(u) tree pre-builds every cluster and sub-cluster whether or not anyone ever uses them — like renting an entire 10,000-room hotel just in case, even if only 12 guests ever check in. The reduced-space vEB (RS-vEB) instead only builds a room once a guest actually arrives, using a hash table keyed by cluster index instead of a dense array.

A plain vEB(u) tree takes Θ(u) space and Θ(u) time just to CREATE (recurrence P(u) = (√u+1)P(√u) + Θ(√u), solvable to P(u) = O(u); an empty RS-vEB tree, by contrast, is created in O(1)). That's fine when n (the number of elements actually stored) is close to u, wasteful when it isn't. The reduced-space vEB tree keeps a summary pointer that starts NIL and a sparse cluster map that only ever contains entries for clusters that have actually received an element — a lookup miss is simply treated as "empty," exactly like a real hash table. RSVEBTree in verify/c20.dart implements exactly this (lazy Map<int, RSVEBTree> instead of a dense array) and is verified to behave identically to the dense VEBTree while using dramatically fewer live nodes (in a seeded test with u = 65536 and 50 insertions, liveNodeCount() was at most about 3.1n, versus 92,007 nodes for a dense tree; proving the tight O(n) bound for insert-only use takes a finer argument).

Dart: the dense space recurrence P(u) = (√u + 1)·P(√u) + √u with P(2) = 1 (u = 2^{(2^k)}); it gives 1, 5, 29, 509, 131069 for u = 2, 4, 16, 256, 65536 and exactly 2u − 3:

Dart: the reduced-space tree (RSVEBTree) — clusters live in a Map and are created on first use; liveNodeCount() counts nodes that really exist:

Input size → what’s feasible: u = 2³² with n = 3·10⁴ keys → at most 12n ≈ 3.6·10⁵ live nodes (measured bound) instead of 6.0·10⁹ for a dense tree; u = 2²⁰ and n = 2000 scores → about 5,000 live nodes instead of 1,421,676.

y-fast tries (D. Willard's structure) reaches the same O(lg lg u) worst case for MEMBER/MIN/MAX/PRED/SUCC and O(lg lg u) AMORTIZED for INSERT/DELETE, using only O(n) space — by combining a perfect hash table of every element's binary PREFIXES (to binary-search over prefix lengths) with groups of lg u elements each kept in a small balanced BST, one "representative" per group filed in the hash table. It's a fundamentally different technique (hashing + binary search over prefix length, rather than recursive clustering) reaching the same asymptotic destination — covered as an Expert-tier interview question below.

Dart: the x-fast trie — every prefix of every key is hashed to the [min, max] below it, and SUCCESSOR/PREDECESSOR binary-search the prefix length with one hash probe per step (≤ ⌈lg(lg u + 1)⌉ = 5 probes for lg u = 16); the sorted list stands for the doubly-linked list of neighbours:

Dart: the y-fast grouping — groups of lg u consecutive keys, only each group’s maximum goes into the x-fast trie (n = 1976 keys, u = 2¹⁶: 124 groups, 1,361 hashed prefixes instead of 12,410):

Input size → what’s feasible: u = 2¹⁶, n = 2000 → x-fast: 12,410 hashed prefixes; y-fast: 1,361 (both for n = 1976 keys); u = 2³² → each query is ≤ ⌈lg 33⌉ = 6 hash probes.

Dense vEB trades O(u) space for guaranteed O(lg lg u) time on every op. Reduced-space vEB (lazy hash-table clusters) avoids the Θ(u) space and creation cost: an empty tree is O(1), and operations take O(lg lg u) expected time; proving O(n) space when elements are never deleted takes a finer argument (each insert creates only O(lg lg u) nodes, so O(n lg lg u) is the easy bound) — in our seeded test with u=65536, n=50 it used at most about 3.1n nodes versus 92,007 for a dense tree. y-fast tries reach O(n) space AND O(lg lg u) worst-case queries via a different construction: perfect hashing over key prefixes.

Quiz

Interview questions

Cheat sheet

Structure / operation	Time	Space	Notes
Direct-address bit vector	MEMBER/INSERT/DELETE Θ(1); MIN/MAX/SUCC/PRED Θ(u) worst case	Θ(u)	Simplest baseline; no structure beyond the raw array
Binary tree of bits	All ops O(lg u); MEMBER O(1)	Θ(u)	Height-lg u OR-tree; better than a bit vector, no worse than a balanced BST for most ops
Degree-√u tree (height 2)	INSERT O(1); MIN/MAX/SUCC/PRED/DELETE O(√u)	Θ(u)	Seeds the recursive-clustering idea; not yet O(lg lg u)
protoMember	O(lg lg u)	Θ(u)	One recursive call/level — achieves the target recurrence
protoMinimum	Θ(lg u)	Θ(u)	Two recursive calls/level (summary then cluster)
protoSuccessor	Θ(lg u · lg lg u)	Θ(u)	Up to 3 calls/level, one of them itself Θ(lg u)
protoInsert	Θ(lg u)	Θ(u)	Always 2 unconditional recursive calls/level
vebMinimum / MAXIMUM	O(1)	—	Plain field reads, no recursion
vebMember	O(lg lg u)	—	Min/max shortcut checked first, then ≤ 1 recursive call
vebSuccessor / PREDECESSOR	O(lg lg u)	—	≤ 1 recursive call/level; PREDECESSOR has one extra v.min fallback case
vebEmptyInsert	O(1)	—	Sets min=max=x; used by both empty-tree INSERT and freshly-seeded clusters
vebInsert	O(lg lg u)	—	≤ 1 true recursive call/level (cluster XOR summary, never both)
vebDelete	O(lg lg u)	—	Cluster + summary recursive calls only co-occur when the cluster just emptied
Full vEB(u) tree (any op)	O(lg lg u)	Θ(u), and Θ(u) just to CREATE	Only worth it when n is not tiny relative to u, or you use the reduced-space variant
Reduced-space vEB (RS-vEB)	O(lg lg u) expected (amortized, hashing)	O(n) if nothing is ever deleted (finer argument); O(n lg lg u) is the easy bound	Lazy Map-based clusters instead of a dense array; O(1) to create empty
x-fast trie	MEMBER O(1) expected; MIN/MAX O(1); PRED/SUCC O(lg lg u); INSERT/DELETE O(lg u)	O(n lg u)	Perfect-hashes every element AND every binary prefix
y-fast trie	MEMBER/MIN/MAX/PRED/SUCC O(lg lg u) worst case; INSERT/DELETE O(lg lg u) amortized	O(n)	Groups of Θ(lg u) elements in small BSTs, cuts x-fast trie’s space to linear
Balanced BST (for comparison)	O(lg n) for every op	O(n)	Works for ANY comparable key, no universe-size assumption needed