101
0/276
Loading content...
Throughout the previous pages, we've stated that trie operations run in O(m) time, where m is the length of the string being inserted, searched, or prefix-checked. Now it's time to rigorously verify this claim, understand its implications, and appreciate why this bound is so powerful.
The key insight isn't just that operations are O(m)—it's that the time is independent of n, the number of strings in the trie. Whether your trie contains 100 words or 100 million words, inserting, searching, or checking a prefix for a 10-character string takes the same time.
This independence from n is what makes tries exceptional for large-scale string processing. In this page, we'll formally analyze each operation, compare tries to alternative data structures, and identify the conditions under which the O(m) bound holds.
By the end of this page, you will: (1) Provide rigorous justification for the O(m) time complexity of each operation, (2) Understand the role of alphabet size in constant factors, (3) Compare trie complexity to hash tables, BSTs, and sorted arrays, (4) Recognize when O(m) truly matters versus when it's comparable to alternatives, (5) Analyze space-time tradeoffs in trie design.
Let's rigorously analyze the time complexity of the insert operation.
Insert(word): Add word to the trie, creating any necessary nodes.
function insert(word):
current = root
for each character c in word: // Loop runs m times
if c not in current.children: // O(1) lookup
create new node // O(1)
current.children[c] = node // O(1)
current = current.children[c] // O(1)
current.isEndOfWord = true // O(1)
Loop iterations: Exactly m (the length of the word).
Work per iteration:
Child lookup: O(1)
children[index] is direct array accesschildren.has(c) is amortized O(1) hash lookupNode creation (if needed): O(1)
Pointer update: O(1)
Total time: O(m × 1) = O(m)
For array-based tries, node creation technically takes O(Σ) time to initialize the children array. However, since Σ (typically 26 or 128) is a constant, this is O(1) in complexity terms. The constant factor matters in practice—creating nodes for Unicode tries (Σ up to 143,859) would be expensive, which is why hash maps are preferred for large alphabets.
New space per insert:
Average case: Depends on prefix overlap in the dictionary. More shared prefixes = less new space per word.
Search(word): Return true if word was previously inserted, false otherwise.
function search(word):
current = root
for each character c in word: // Loop runs at most m times
if c not in current.children: // O(1) lookup
return false // Early exit
current = current.children[c] // O(1)
return current.isEndOfWord // O(1)
Loop iterations: At most m (may exit early if path breaks).
Work per iteration:
Final isEndOfWord check: O(1)
Total time: O(m × 1 + 1) = O(m)
Best case: O(1)
Worst case: O(m)
Average case: O(m) or less
Auxiliary space: O(1)
Search is a purely read-only operation that doesn't modify the trie.
StartsWith(prefix): Return true if any word in the trie starts with prefix.
function startsWith(prefix):
current = root
for each character c in prefix: // Loop runs at most m times
if c not in current.children: // O(1) lookup
return false // Early exit
current = current.children[c] // O(1)
return true // Path exists
Identical to search, minus the isEndOfWord check:
Total time: O(m) where m is the prefix length
Algorithmically, startsWith is simpler:
Both are O(m). The semantic difference is profound; the complexity difference is negligible.
The O(m) complexity has a remarkable property: it is independent of n (the number of strings in the trie).
Consider two scenarios:
For a 10-character query:
The trie doesn't slow down as it grows. This is fundamentally different from most search data structures.
In a trie, the path you walk depends only on the query string, not on what other strings exist. Whether there are 1 million other words or 0 other words, your path is determined solely by the characters in your query. This is why complexity depends only on m.
While O(m) is independent of n, it hides a dependency on alphabet size Σ in the constant factors:
Array-based tries:
Hash map-based tries:
For fixed, small alphabets (lowercase English, ASCII), this is a non-issue. For Unicode or very large character sets, the constant factors become significant.
Although O(m) sounds efficient, consider:
Very long strings: For m = 1000 characters, every operation touches 1000 nodes. For databases of URLs, filepaths, or DNA sequences, m can be large.
Many short queries: For autocomplete with single-character typing, m = 1 is tiny, and the constant overhead of function calls may dominate.
Combined with other operations: Building a trie from n strings of average length L takes O(n × L) total time.
Let's rigorously compare trie complexity against other string-storing data structures. We'll use:
| Data Structure | Time Complexity | Reasoning |
|---|---|---|
| Trie | O(m) | Walk/create m nodes |
| Hash Set | O(m) | O(m) to hash + O(1) to insert |
| Balanced BST (Tree Set) | O(m × log n) | O(log n) comparisons × O(m) per comparison |
| Sorted Array | O(m + n) | O(n) shift + O(m) for comparison |
| Unsorted Array | O(m) | O(1) append (assuming copy of string) |
Analysis:
| Data Structure | Time Complexity | Reasoning |
|---|---|---|
| Trie | O(m) | Walk m nodes, check end-of-word |
| Hash Set | O(m) | O(m) to hash + O(1) lookup |
| Balanced BST | O(m × log n) | O(log n) comparisons × O(m) per comparison |
| Sorted Array + Binary Search | O(m × log n) | O(log n) comparisons × O(m) per comparison |
| Unsorted Array | O(n × m) | O(n) entries × O(m) comparison each |
Analysis:
| Data Structure | Query: startsWith | Query: getAllWithPrefix |
|---|---|---|
| Trie | O(m) | O(m + output) |
| Hash Set | O(n × m) | O(n × m) |
| Balanced BST | O(m × log n + output) | O(m × log n + output) |
| Sorted Array | O(m × log n + output) | O(m × log n + output) |
| Unsorted Array | O(n × m) | O(n × m) |
For prefix operations, tries are O(m) while hash sets are O(n × m). For n = 1,000,000 and m = 5, that's 5 operations vs 5,000,000 operations—a million-fold difference. This is why autocomplete systems use tries, not hash tables.
When hash sets are better:
When tries are better:
Real applications don't perform single operations—they batch them. Let's analyze aggregate complexity.
If we insert n strings with lengths L₁, L₂, ..., Lₙ:
Total time: O(L₁ + L₂ + ... + Lₙ) = O(L), where L is the total length of all strings.
If average length is L̄ = L/n:
Total time: O(n × L̄) = O(nL̄)
Example:
For k queries with lengths m₁, m₂, ..., mₖ:
Total time: O(m₁ + m₂ + ... + mₖ)
If query length is bounded by some constant M:
Total time: O(k × M) = O(k)
Key insight: Query time doesn't grow with trie size. A trie with 1 million words and a trie with 1 billion words answer queries in the same time.
| Operation Set | Time Complexity | Space Complexity |
|---|---|---|
| Build trie (n strings, total length L) | O(L) | O(L × Σ) array / O(L) hash |
| k exact searches (lengths m₁...mₖ) | O(Σmᵢ) | O(1) |
| k prefix queries (lengths m₁...mₖ) | O(Σmᵢ) | O(1) |
| Enumerate all words in trie | O(total characters) | O(max word length) stack |
The O(m) time guarantee comes with space considerations. Let's analyze the tradeoffs.
Time: Absolute O(1) child lookup (single array access)
Space per node: O(Σ) where Σ is alphabet size
Total space: O(N × Σ) where N is total number of nodes
When to use: Small, fixed alphabet; speed-critical applications
Time: O(1) average, but with hashing overhead
Space per node: O(actual children)
Total space: O(N + edges) ≈ O(total characters)
When to use: Large or variable alphabets; memory-constrained applications
| Aspect | Array-Based | Hash Map-Based |
|---|---|---|
| Child lookup | O(1) with ~3 CPU instructions | O(1) avg with ~20+ CPU instructions |
| Memory for sparse node | O(Σ) always | O(children) |
| Memory for dense node | O(Σ) | O(Σ) + overhead |
| Cache locality | Excellent (contiguous) | Poor (hash buckets) |
| Alphabet flexibility | Fixed at construction | Fully flexible |
For most applications (lowercase dictionary, URLs, file paths), hash map-based tries provide the best balance. Use array-based tries only when you've profiled and confirmed that the constant factors in hash lookups are a bottleneck, AND you have memory to spare for the alphabet-sized arrays.
Standard tries can waste space on single-child chains:
a → p → p → l → e (5 nodes for "apple" with no branching)
Radix trees compress these chains:
"apple" (1 node with edge label "apple")
Trade-off:
We'll explore compressed tries in the advanced module.
O(m) is theoretically optimal for string operations (you must at least read the input), but practical scenarios introduce additional factors.
For very large tries (billions of nodes), memory access patterns matter:
Mitigation: Cache-oblivious layouts, compressed tries, memory-mapped files
Multiple threads reading/writing a trie:
Mitigation: Read-copy-update patterns, lock-free concurrent tries
Storing tries on disk:
Mitigation: Serialized trie formats, memory-mapped files, succinct tries
Remember that O(m) describes asymptotic behavior, not wall-clock time. A trie with O(m) complexity can be slower in practice than a hash table with O(m) complexity if the constant factors differ significantly. Always profile with realistic data before choosing a data structure for performance-critical applications.
We've rigorously analyzed the time complexity of trie operations. Here are the essential takeaways:
Module Complete!
You've now mastered the three fundamental trie operations—insert, search, and startsWith—along with their O(m) time complexity. This completes the operational foundation for working with tries.
In subsequent modules, we'll explore:
Congratulations! You've completed Module 4: Trie Operations. You can now implement insert, search, and startsWith with confidence, explain their O(m) complexity, and articulate when tries outperform alternative data structures. You're equipped to build efficient string-processing systems using tries.