UPD : RESULTS ARE OUT!!!

Space Complexity of a Trie

Most blogs state that the space complexity of a trie is

where:

• $$$N$$$ = number of strings
• $$$L$$$ = maximum length of a string
• $$$R$$$ = alphabet size (typically $$$26$$$ for lowercase letters)

This is usually justified by:

• The trie can have at most $$$L$$$ levels
• Each string contributes at most one node per level
• Each node stores an array of size $$$R$$$

Hence:

However, this is a very loose bound. Let us analyze this carefully.

Key Observation

At depth $$$d$$$, the number of distinct nodes is at most

because:

• Each node represents a unique prefix of length $$$d$$$
• There are at most $$$R^d$$$ possible prefixes at depth $$$d$$$
• And we cannot have more nodes than strings ($$$N$$$)

Example Calculation

Assume:

Compute nodes per level:

From level 5 onward, the number of nodes is capped by $$$N$$$.

Total Number of Nodes

Let us count nodes:

• Levels 0 to 4: $$$26^0 + 26^1 + 26^2 + 26^3 + 26^4$$$
• Levels 5 to $$$L-1$$$: each can have at most $$$N$$$ nodes

Hence, total nodes:

(We use $$$L-4$$$ because the first 4 levels are counted separately: 1,2,3,4 → 4 levels, so remaining $$$L-4$$$ levels are “full” levels capped by $$$N$$$.)

Total Space Usage

Each node stores an array of size $$$R = 26$$$, so total memory:

Comparison With Naive Bound

Naive bound:

We compare the prefix contribution:

Compute sum:

For $$$N = 10^6$$$:

✅ True.

Hence, the naive bound overestimates memory by about 8×, because it assumes $$$N$$$ nodes at each level, while in reality early levels have far fewer nodes.

Tight Space Complexity

In general, the tight upper bound on the number of nodes is:

So total space:

For fixed alphabet size $$$R$$$:

Takeaway

• $$$O(N \cdot L \cdot R)$$$ is a very loose bound
• Early levels of the trie have far fewer nodes than $$$N$$$
• Real space usage is often ~8× smaller than the naive calculation
• Correct intuition: $$$\min(N, R^d)$$$ nodes at depth $$$d$$$