Longest Common Prefix in DSA Python - Time & Space Complexity

Time Complexity: Longest Common Prefix

O(n * m)

Understanding Time Complexity

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

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

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def longest_common_prefix(strs):
    if not strs:
        return ""
    prefix = strs[0]
    for s in strs[1:]:
        while not s.startswith(prefix):
            prefix = prefix[:-1]
            if not prefix:
                return ""
    return prefix

This code finds the longest common prefix string among a list of strings by comparing and shortening the prefix as needed.

Identify Repeating Operations

• Primary operation: Checking if each string starts with the current prefix and shortening the prefix.
• How many times: For each string, the prefix may be shortened multiple times, up to the length of the prefix.

How Execution Grows With Input

As the number of strings (n) or the length of the prefix (m) grows, the work increases roughly by n times m.

Input Size (n strings, m length)	Approx. Operations
10 strings, prefix length 5	About 50 checks
100 strings, prefix length 10	About 1000 checks
1000 strings, prefix length 20	About 20,000 checks

Pattern observation: The operations grow roughly by multiplying the number of strings by the prefix length.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally with the number of strings and the length of the prefix we check.

Common Mistake

[X] Wrong: "The time is just O(n) because we only loop through the list once."

[OK] Correct: Each string comparison can take up to the length of the prefix, so the inner work depends on prefix length too.

Interview Connect

Understanding this helps you explain how nested checks affect performance and shows you can analyze combined factors, a key skill in interviews.

Self-Check

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