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

Time Complexity: Word Search in Trie

O(m)

Understanding Time Complexity

When searching for a word in a Trie, we want to know how long it takes as the word gets longer.

We ask: How does the search time grow when the word length increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function searchWord(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 given 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: Loop over each character in the word.
• How many times: Once for each character in the word (word length).

How Execution Grows With Input

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

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

Pattern observation: The number of operations 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

Understanding 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 nodes used arrays instead of hash maps for children? How would the time complexity change?"