Autocomplete System with Trie in DSA C++ - Time & Space Complexity

Time Complexity: Autocomplete System with Trie

O(k)

Understanding Time Complexity

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

How does the time to find suggestions grow as the prefix or dictionary size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct TrieNode {
    TrieNode* children[26] = {nullptr};
    bool isWord = false;
};

void insert(TrieNode* root, const std::string& word) {
    TrieNode* node = root;
    for (char c : word) {
        int idx = c - 'a';
        if (!node->children[idx])
            node->children[idx] = new TrieNode();
        node = node->children[idx];
    }
    node->isWord = true;
}

TrieNode* searchPrefix(TrieNode* root, const std::string& prefix) {
    TrieNode* node = root;
    for (char c : prefix) {
        int idx = c - 'a';
        if (!node->children[idx])
            return nullptr;
        node = node->children[idx];
    }
    return node;
}
    

This code inserts words into a trie and searches for the node matching a prefix.

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, so the number of characters in the word or prefix (let's call it k).

How Execution Grows With Input

As the prefix length k grows, the search checks one more character each time.

Input Size (prefix length k)	Approx. Operations
10	About 10 character checks
100	About 100 character checks
1000	About 1000 character checks

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

Final Time Complexity

Time Complexity: O(k)

This means the time to find the prefix node grows only with the length of the prefix, 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 want to list all words starting with the prefix? How would that affect the time complexity?"