Prefix Search Using Trie in DSA Typescript - Time & Space Complexity

Time Complexity: Prefix Search Using Trie

O(m)

Understanding Time Complexity

We want to understand how fast we can find words that start with a given prefix using a Trie.

The question is: how does the search time grow as the prefix length or number of words changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class TrieNode {
  children: Map = new Map();
  isWord: boolean = false;
}

function startsWith(root: TrieNode, prefix: string): boolean {
  let node = root;
  for (const char of prefix) {
    if (!node.children.has(char)) return false;
    node = node.children.get(char)!;
  }
  return true;
}
    

This code checks if any word in the Trie starts with the given prefix by following nodes for each prefix character.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

Each character in the prefix requires one step to check in the Trie.

Input Size (prefix length m)	Approx. Operations
10	10 steps
100	100 steps
1000	1000 steps

Pattern observation: The time grows linearly with the prefix length, not with the total number of words stored.

Final Time Complexity

Time Complexity: O(m)

This means the search time depends only on how long the prefix is, not on how many words are in the Trie.

Common Mistake

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

[OK] Correct: The search only follows nodes for the prefix characters, so it depends on prefix length, not total words.

Interview Connect

Understanding this helps you explain why Tries are efficient for prefix searches, a common real-world problem like autocomplete.

Self-Check

"What if we changed the prefix search to also return all words starting with the prefix? How would the time complexity change?"