Longest Word in Dictionary Using Trie in DSA Typescript - Time & Space Complexity

Time Complexity: Longest Word in Dictionary Using Trie

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to find the longest word using a Trie grows as the dictionary size increases.

Specifically, how the operations scale when building and searching the Trie.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

function insert(root: TrieNode, word: string): void {
  let node = root;
  for (const char of word) {
    if (!node.children.has(char)) node.children.set(char, new TrieNode());
    node = node.children.get(char)!;
  }
  node.isWord = true;
}
    

This code inserts words into a Trie, letter by letter, marking the end of each word.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character of every word to insert into the Trie.
• How many times: For each of the n words, we loop through its length m characters.

How Execution Grows With Input

As the number of words (n) and their average length (m) grow, the total operations increase roughly by n times m.

Input Size (n words, avg length m)	Approx. Operations
10 words, length 5	~50 operations
100 words, length 5	~500 operations
1000 words, length 5	~5000 operations

Pattern observation: Operations grow linearly with both number of words and their length.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the total number of characters in all words combined.

Common Mistake

[X] Wrong: "Inserting all words into a Trie is just O(n) because we only loop over words once."

[OK] Correct: Each word has multiple characters, so we actually loop over every character in every word, making it O(n * m), not just O(n).

Interview Connect

Understanding this complexity helps you explain how Tries efficiently handle many words and why they are preferred for prefix-based problems.

Self-Check

What if we changed the data structure to a simple array and searched for the longest word by checking prefixes? How would the time complexity change?