Word Search in Trie in DSA Go - Time & Space Complexity

Time Complexity: Word Search in Trie

O(n)

Understanding Time Complexity

We want to understand how long it takes to search for a word in a Trie data structure.

The question is: how does the search time grow as the word length increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func (t *TrieNode) Search(word string) bool {
    current := t
    for _, ch := range word {
        if current.children[ch-'a'] == nil {
            return false
        }
        current = current.children[ch-'a']
    }
    return current.isEnd
}
    

This code checks if a given word exists in the Trie by following nodes for each letter.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character of the word.
• How many times: Exactly once per character in the word (word length).

How Execution Grows With Input

As the word gets longer, the search checks one more node for each letter.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The operations grow linearly with the word length.

Final Time Complexity

Time Complexity: O(n)

This means the search time grows directly with the length of the word you are looking for.

Common Mistake

[X] Wrong: "Searching a word in a Trie takes time proportional to the number of words stored."

[OK] Correct: The search depends only on the length of the word, not how many words are in the Trie.

Interview Connect

Knowing this helps you explain why Tries are efficient for prefix and word searches, a common topic in coding interviews.

Self-Check

"What if the Trie stored Unicode characters instead of only lowercase letters? How would the time complexity change?"