Prefix Search Using Trie in DSA C++ - Time & Space Complexity

Time Complexity: Prefix Search Using Trie

O(m)

Understanding Time Complexity

We want to understand how fast we can find words that start with a given prefix using a Trie.

How does the search time change as the prefix length or number of words grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

bool startsWith(TrieNode* root, const std::string& prefix) {
    TrieNode* node = root;
    for (char c : prefix) {
        if (!node->children[c - 'a'])
            return false;
        node = node->children[c - 'a'];
    }
    return true;
}
    

This code checks if any word in the Trie starts with the given prefix by following nodes for each prefix character.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over each character in the prefix string.
• How many times: Exactly once per character in the prefix (length m).

How Execution Grows With Input

The time grows directly with the length of the prefix we search for.

Input Size (prefix length m)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The time increases linearly as the prefix length increases.

Final Time Complexity

Time Complexity: O(m)

This means the search time depends only on the prefix length, not on the number of words stored.

Common Mistake

[X] Wrong: "The search time depends on the total number of words in the Trie."

[OK] Correct: The search only follows nodes for the prefix characters, so it depends on prefix length, not total words.

Interview Connect

Knowing how prefix search scales helps you explain why Tries are efficient for autocomplete and dictionary lookups.

Self-Check

"What if the Trie stored uppercase and lowercase letters separately? How would the time complexity change?"