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

Time Complexity: Count Words with Given Prefix

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to count words with a given prefix changes as the number of words grows.

Specifically, how does the search for words starting with a prefix affect performance?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function countWordsWithPrefix(words: string[], prefix: string): number {
  let count = 0;
  for (const word of words) {
    if (word.startsWith(prefix)) {
      count++;
    }
  }
  return count;
}
    

This code counts how many words in the list start with the given prefix by checking each word one by one.

Identify Repeating Operations

• Primary operation: Looping through each word and checking if it starts with the prefix.
• How many times: Once for every word in the list (n times).

How Execution Grows With Input

As the number of words increases, the time to check all words grows roughly in direct proportion.

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

Pattern observation: Doubling the number of words roughly doubles the work done.

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 is checked against the prefix.

Common Mistake

[X] Wrong: "Checking prefix is always O(1) so total time is just O(n)."

[OK] Correct: Checking if a word starts with a prefix takes time proportional to the prefix length, so it depends on both n and m.

Interview Connect

Understanding how prefix checks scale helps you explain trade-offs in searching and string matching, a common topic in interviews.

Self-Check

"What if we used a trie (prefix tree) instead of checking each word? How would the time complexity change?"