Time Complexity: Trie vs Hash Map for Prefix Matching
O(m) for trie search, O(n x m) for hash map search
0
0
Trie vs Hash Map for Prefix Matching in DSA Javascript - Complexity Comparison
Understanding Time Complexity
We want to compare how fast tries and hash maps find words starting with a prefix.
How does the time to find matches grow as we add more words or longer prefixes?
Scenario Under Consideration
Analyze the time complexity of prefix search using a trie and a hash map.
// Trie prefix search
function trieSearch(root, prefix) {
let node = root;
for (const char of prefix) {
if (!node.children[char]) return [];
node = node.children[char];
}
return collectWords(node);
}
// Hash map prefix search
function hashMapSearch(words, prefix) {
return words.filter(word => word.startsWith(prefix));
}
The trie search walks down nodes for each prefix letter. The hash map search checks every word.
Identify Repeating Operations
Look at what repeats most in each method.
- Trie search primary operation: Loop over prefix letters to go down trie nodes.
- Trie search times: Once per prefix letter (length m).
- Hash map search primary operation: Loop over all words to check prefix.
- Hash map search times: Once per word (n words), each check up to prefix length m.
How Execution Grows With Input
How does work grow as input grows?
| Input Size (n words) | Trie Search (prefix length m=3) | Hash Map Search (prefix length m=3) |
|---|---|---|
| 10 | 3 steps down trie | 10 words x 3 chars = 30 checks |
| 100 | 3 steps down trie | 100 words x 3 chars = 300 checks |
| 1000 | 3 steps down trie | 1000 words x 3 chars = 3000 checks |
Trie search time depends only on prefix length, stays small as words grow.
Hash map search time grows linearly with number of words times prefix length.
Final Time Complexity
Time Complexity: O(m) for trie search, O(n x m) for hash map search
Trie search time grows with prefix length only, hash map search grows with total words and prefix length.
Common Mistake
[X] Wrong: "Hash map search is always faster because hash maps are quick."
[OK] Correct: Hash maps are fast for exact keys, but prefix search needs checking many words, so it slows down as word list grows.
Interview Connect
Understanding these differences helps you choose the right tool for prefix search tasks in real projects.
Self-Check
What if we stored all prefixes in the hash map as keys? How would that change the time complexity?