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

Time Complexity: Count Words with Given Prefix

O(n * m)

Understanding Time Complexity

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

The question is: how does the time grow when the list or prefix size changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

func countPrefix(words []string, prefix string) int {
    count := 0
    for _, word := range words {
        if len(word) >= len(prefix) && word[:len(prefix)] == prefix {
            count++
        }
    }
    return count
}
    

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

Identify Repeating Operations

• Primary operation: Looping through each word in the list.
• How many times: Once for each word, so as many times as the list size (n).
• Secondary operation: Checking prefix by comparing characters up to prefix length (m).
• How many times: Up to prefix length for each word.

How Execution Grows With Input

As the number of words (n) grows, the loop runs more times. Also, longer prefixes (m) mean more characters to check per word.

Input Size (n)	Prefix Length (m)	Approx. Operations
10	3	About 10 * 3 = 30 checks
100	3	About 100 * 3 = 300 checks
1000	3	About 1000 * 3 = 3000 checks

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

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the number of words times the length of the prefix.

Common Mistake

[X] Wrong: "Checking prefix is always O(1) because prefix is small."

[OK] Correct: Even if prefix is small, it still requires checking each character for every word, so it depends on prefix length and number of words.

Interview Connect

Understanding how loops and string checks combine helps you explain your code clearly and shows you know how to analyze performance in real tasks.

Self-Check

"What if we stored words in a trie data structure? How would the time complexity change when counting words with a prefix?"