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

Time Complexity: Autocomplete System with Trie

O(m)

Understanding Time Complexity

We want to know how fast the autocomplete system finds suggestions as we type more letters.

How does the time to get suggestions grow when the input or dictionary size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class TrieNode {
  constructor() {
    this.children = {};
    this.isWord = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const char of word) {
      if (!node.children[char]) node.children[char] = new TrieNode();
      node = node.children[char];
    }
    node.isWord = true;
  }

  searchPrefix(prefix) {
    let node = this.root;
    for (const char of prefix) {
      if (!node.children[char]) return null;
      node = node.children[char];
    }
    return node;
  }
}
    

This code builds a trie and finds the node matching a prefix to start autocomplete suggestions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character of the input word or prefix.
• How many times: Once per character in the word or prefix (length m).
• Autocomplete suggestions may involve traversing nodes below the prefix node, but this snippet focuses on prefix search.

How Execution Grows With Input

Time grows with the length of the prefix typed, not the total number of words stored.

Input Size (prefix length m)	Approx. Operations
3	3 steps to follow nodes
5	5 steps to follow nodes
10	10 steps to follow nodes

Pattern observation: The time increases linearly with prefix length, independent of dictionary size.

Final Time Complexity

Time Complexity: O(m)

This means the search time grows only with how many letters you type, not 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 nodes for the prefix letters, so it depends on prefix length, not dictionary size.

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 added a step to collect all words below the prefix node? How would that affect time complexity?"