Longest Common Prefix in DSA C - Time & Space Complexity

Time Complexity: Longest Common Prefix

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to find the longest common prefix changes as we add more words or longer words.

How does the work grow when the input list or word length grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

char* longestCommonPrefix(char** strs, int strsSize) {
    if (strsSize == 0) return "";
    if (strsSize == 1) return strs[0];
    for (int i = 0; ; i++) {
        char c = strs[0][i];
        for (int j = 1; j < strsSize; j++) {
            if (strs[j][i] == '\0' || strs[j][i] != c) {
                strs[0][i] = '\0';
                return strs[0];
            }
        }
    }
}
    

This code finds the longest common prefix among an array of strings by comparing characters one by one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops comparing characters of each string at the same position.
• How many times: Outer loop runs up to the length of the shortest string; inner loop runs for each string in the array.

How Execution Grows With Input

As we add more strings or longer strings, the comparisons increase.

Input Size (n = number of strings)	Approx. Operations
10 strings, each length 5	About 50 character comparisons
100 strings, each length 5	About 500 character comparisons
100 strings, each length 100	Up to 10,000 character comparisons

Pattern observation: The work grows roughly with the product of the number of strings and the length of the shortest string.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows with the number of strings (n) times the length of the shortest string (m).

Common Mistake

[X] Wrong: "The time depends only on the number of strings, not their length."

[OK] Correct: We must check characters one by one, so longer strings mean more work even if the number of strings stays the same.

Interview Connect

Understanding this helps you explain how your solution scales and shows you can analyze nested loops clearly.

Self-Check

"What if we sorted the strings first and only compared the first and last strings? How would the time complexity change?"