Trie vs Hash Map for Prefix Matching in DSA C++ - Complexity Comparison

Time Complexity: Trie vs Hash Map for Prefix Matching

O(m) for Trie, O(n * m) for Hash Map

Understanding Time Complexity

We want to understand how fast we can find words that start with a given prefix using two common data structures.

Which one is faster when the input grows: a Trie or a Hash Map?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Trie prefix search
bool startsWith(TrieNode* root, const string& prefix) {
    TrieNode* node = root;
    for (char c : prefix) {
        if (!node->children.count(c)) return false;
        node = node->children[c];
    }
    return true;
}

// Hash Map prefix search
bool startsWithHashMap(const unordered_map<string, bool>& wordsMap, const string& prefix) {
    for (const auto& [word, _] : wordsMap) {
        if (word.compare(0, prefix.size(), prefix) == 0) return true;
    }
    return false;
}
    

The first function checks if any word in the Trie starts with the prefix by walking down nodes.

The second function checks each word in the hash map to see if it starts with the prefix.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation in Trie: Loop over prefix characters.
• How many times: Once per character in prefix (length m).
• Primary operation in Hash Map: Loop over all words, then compare prefix.
• How many times: For n words, each comparison up to m characters.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations Trie	Approx. Operations Hash Map
10	~m (prefix length)	10 * m
100	~m	100 * m
1000	~m	1000 * m

Pattern observation: Trie operations grow only with prefix length, while Hash Map operations grow with number of words times prefix length.

Final Time Complexity

Time Complexity: O(m) for Trie, O(n * m) for Hash Map

This means Trie searches grow only with prefix length, while Hash Map searches grow with total words and prefix length.

Common Mistake

[X] Wrong: "Hash Map prefix search is always faster because hash lookups are quick."

[OK] Correct: Hash Maps are fast for exact keys, but checking prefixes requires scanning many keys, which slows down as word count grows.

Interview Connect

Knowing when to use a Trie or Hash Map for prefix matching shows you understand trade-offs in data structures and efficiency.

Self-Check

"What if we stored all prefixes as keys in the Hash Map? How would that change the time complexity for prefix search?"