Prefix Search Using Trie in DSA Go - 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.

The question is: How does the search time grow as the prefix length or number of words changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// SearchPrefix returns true if prefix exists in Trie
func (t *Trie) SearchPrefix(prefix string) bool {
    node := t.root
    for _, ch := range prefix {
        if node.children[ch] == nil {
            return false
        }
        node = node.children[ch]
    }
    return true
}
    

This code checks if a given prefix exists by walking down the Trie nodes for each 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

As the prefix length grows, the search checks more nodes one by one.

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

Pattern observation: The operations grow linearly with prefix length.

Final Time Complexity

Time Complexity: O(m)

This means the search time grows directly with the length of the prefix, not 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 the prefix characters, so it depends on prefix length, not total words.

Interview Connect

Knowing this helps you explain why Tries are efficient for prefix searches, a common real-world problem like autocomplete.

Self-Check

"What if the Trie stored words with very long alphabets (like Unicode)? How would that affect the time complexity?"