Trie Search Operation in DSA Go - Time & Space Complexity

Time Complexity: Trie Search Operation

O(n)

Understanding Time Complexity

We want to know how long it takes to find a word in a trie.

How does the search time change when the word gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func (t *Trie) Search(word string) bool {
    node := t.root
    for _, ch := range word {
        if node.children[ch] == nil {
            return false
        }
        node = node.children[ch]
    }
    return node.isEnd
}
    

This code checks if a word exists in the trie by following each character step-by-step.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

Each extra character means one more step to check in the trie.

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

Pattern observation: The number of steps grows directly with the word length.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Searching a trie depends on the total number of words stored."

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

Interview Connect

Knowing trie search time helps you explain efficient word lookups and autocomplete features clearly.

Self-Check

"What if we changed the trie to store only lowercase letters instead of all characters? How would the time complexity change?"