Autocomplete System with Trie in DSA Go - Time & Space Complexity

Time Complexity: Autocomplete System with Trie

O(p + m)

Understanding Time Complexity

We want to understand how fast an autocomplete system using a trie can find suggestions.

How does the time to find words grow as we add more words or type more letters?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Search for words starting with prefix in trie
func (t *Trie) SearchPrefix(prefix string) []*TrieNode {
    node := t.root
    for _, ch := range prefix {
        if node.children[ch-'a'] == nil {
            return nil
        }
        node = node.children[ch-'a']
    }
    return collectWords(node)
}

func collectWords(node *TrieNode) []*TrieNode {
    // Collect all words under this node
    // ... (recursive traversal)
    return nil // placeholder to avoid syntax error
}
    

This code finds the node matching the prefix, then collects all words below it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over prefix characters and recursive traversal of trie nodes.
• How many times: Loop runs once per prefix letter; recursion visits all descendant nodes for suggestions.

How Execution Grows With Input

Typing more letters means the loop runs more times, but fewer words match, so recursion visits fewer nodes.

Input Size (n)	Approx. Operations
Prefix length 3, 1000 words	3 + visits to matching subtree nodes
Prefix length 5, 1000 words	5 + fewer subtree nodes visited
Prefix length 5, 10,000 words	5 + more subtree nodes visited

Pattern observation: More prefix letters mean more initial steps but fewer words to check; more words stored means bigger subtree to explore.

Final Time Complexity

Time Complexity: O(p + m)

This means the time grows with the prefix length p plus the number of matched words m found below.

Common Mistake

[X] Wrong: "The search time depends only on the number of words stored."

[OK] Correct: The search depends mainly on prefix length and matched words, not total words stored.

Interview Connect

Understanding this helps you explain how tries speed up prefix searches, a common real-world feature like search suggestions.

Self-Check

"What if we changed the trie to store counts at each node to avoid recursion? How would the time complexity change?"