Trie insertion and search in Data Structures Theory - Time & Space Complexity

Time Complexity: Trie insertion and search

O(n)

Understanding Time Complexity

When working with tries, it is important to understand how the time to insert or search words grows as the words get longer.

We want to know how the number of steps changes when we add longer words or more words.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

    def search(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end

This code inserts words into a trie and searches for words by following nodes for each character.

Identify Repeating Operations

• Primary operation: Looping through each character of the input word.
• How many times: Once for each character in the word (length n).

How Execution Grows With Input

Each step processes one character, so the total steps grow directly with the word length.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: The time grows linearly as the word length increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to insert or search grows directly with the length of the word.

Common Mistake

[X] Wrong: "Trie operations depend on the number of words stored, so more words always mean slower insert or search."

[OK] Correct: Actually, insert and search time depends mainly on the length of the word, not how many words are stored.

Interview Connect

Understanding trie time complexity helps you explain why tries are efficient for prefix searches and autocomplete features.

Self-Check

"What if we changed the trie to store only lowercase letters and used a fixed-size array instead of a dictionary for children? How would the time complexity change?"