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

Time Complexity: Count Words with Given Prefix

O(n x m)

Understanding Time Complexity

We want to understand how the time needed to count words with a certain prefix grows as the list of words gets bigger.

How does the number of steps change when we have more words or longer prefixes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function countWordsWithPrefix(words, prefix) {
  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.

Identify Repeating Operations

• Primary operation: Checking each word to see if it starts with the prefix.
• How many times: Once for every word in the list (n times).
• Inside each check: Comparing characters of the prefix with the start of the word (up to prefix length m).

How Execution Grows With Input

As the number of words (n) grows, the code checks each word once. For each word, it compares up to m characters where m is the prefix length.

Input Size (n)	Approx. Operations (checks x prefix length)
10	10 x m
100	100 x m
1000	1000 x m

Pattern observation: The total work grows linearly with the number of words and also depends on the prefix length.

Final Time Complexity

Time Complexity: O(n x m)

This means the time grows proportionally to the number of words and the length of the prefix we check.

Common Mistake

[X] Wrong: "Checking the prefix is just O(1) because prefix length is small and fixed."

[OK] Correct: Even if prefix is short, it still takes time proportional to its length for each word, so prefix length matters in total time.

Interview Connect

Understanding how loops and string checks add up helps you explain your code clearly and shows you can think about efficiency in real problems.

Self-Check

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