Question 1335

A Hundred Four Megabytes

A trie over lowercase English stores 200,000 words with 10610^6 characters in total. Nothing is shared in the worst case, so assume about 10610^6 nodes. The node is

struct Node {
    int next[26];   // child index, or -1
    bool isWord;
};

with sizeof(int) == 4. Roughly how much memory do the next arrays alone take, and what is the usual response when that exceeds the limit?

A

About 208 MB, because each child link is a pointer and pointers are 8 bytes on a 64-bit target.

B

About 104 MB. Swap next for a hash map or a sorted list per node, trading O(1) child lookup for O(log k) but dropping the per-node cost to what is actually used.

C

About 26 MB. Nothing needs to change at a typical 256 MB limit.

D

About 4 MB, since the array is one allocation per node rather than 26.