Trie Search Operation in DSA Javascript - Time & Space Complexity

Time Complexity: Trie Search Operation

O(m)

Understanding Time Complexity

We want to understand how long it takes to find a word in a trie. This helps us know how fast searches are as words get longer.

The question is: How does search time grow when the word length changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function search(root, word) {
  let node = root;
  for (let char of word) {
    if (!node.children[char]) {
      return false;
    }
    node = node.children[char];
  }
  return node.isEndOfWord === true;
}
    

This code checks if a word exists in a trie by moving through 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: Once for every letter in the word (word length).

How Execution Grows With Input

As the word gets longer, the search checks more letters one by one.

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

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

Final Time Complexity

Time Complexity: O(m)

This means the search time grows linearly with the length of the word being searched.

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 trie search time helps you explain why tries are fast for prefix searches and autocomplete features. This skill shows you understand efficient word lookups.

Self-Check

"What if the trie stored words with very long common prefixes? How would that affect the search time complexity?"