Count Words with Given Prefix in DSA C++ - Time & Space Complexity

Time Complexity: Count Words with Given Prefix

O(n * m)

Understanding Time Complexity

We want to know how long it takes to count words that start with a certain prefix in a list.

How does the time needed change when the list grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int countWordsWithPrefix(const std::vector<std::string>& words, const std::string& prefix) {
    int count = 0;
    for (const auto& word : words) {
        if (word.compare(0, prefix.size(), prefix) == 0) {
            count++;
        }
    }
    return count;
}
    

This code counts how many words in the list start with the given prefix.

Identify Repeating Operations

• Primary operation: Loop through all words and compare prefix with each word's start.
• How many times: Once for each word in the list (n times).

How Execution Grows With Input

As the number of words grows, the time to check all words grows too.

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

Pattern observation: The operations grow directly with the number of words; doubling words doubles work.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows with the number of words (n) and the length of the prefix (m), because each word's start is checked against the prefix.

Common Mistake

[X] Wrong: "Checking the prefix is always O(1) so the whole is O(n)."

[OK] Correct: Each prefix check compares up to m characters, so it takes O(m) time, not constant time.

Interview Connect

Understanding how loops and string comparisons affect time helps you explain and improve search tasks in real projects.

Self-Check

"What if the words were stored in a trie data structure? How would the time complexity change?"