Autocomplete System with Trie in DSA Typescript - Time & Space Complexity

Time Complexity: Autocomplete System with Trie

O(m)

Understanding Time Complexity

We want to understand how fast an autocomplete system using a trie can find suggestions.

The question is: how does the time to find words grow as we add more words or type longer prefixes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

function searchPrefix(root: TrieNode, prefix: string): TrieNode | null {
  let node = root;
  for (const char of prefix) {
    if (!node.children.has(char)) return null;
    node = node.children.get(char)!;
  }
  return node;
}
    

This code finds the node in the trie that matches the given prefix, if it exists.

Identify Repeating Operations

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

How Execution Grows With Input

As the prefix length grows, the search takes longer, but it does not depend on the total number of words stored.

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

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

Final Time Complexity

Time Complexity: O(m)

This means the search time grows only with how long the prefix is, regardless of how many words are stored.

Common Mistake

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

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

Interview Connect

Understanding this helps you explain why tries are efficient for autocomplete, showing you know how data structure choice affects speed.

Self-Check

"What if we also count the time to collect all words under the prefix node? How would the time complexity change?"