String comparison - Time & Space Complexity

Time Complexity: String comparison

O(n)

Understanding Time Complexity

When we compare two strings in C, we want to know how long it takes as the strings get longer.

We ask: How does the work grow when the strings grow?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int stringCompare(const char *str1, const char *str2) {
    int i = 0;
    while (str1[i] != '\0' && str2[i] != '\0') {
        if (str1[i] != str2[i]) {
            return str1[i] - str2[i];
        }
        i++;
    }
    return str1[i] - str2[i];
}
    

This code compares two strings character by character until it finds a difference or reaches the end.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing characters one by one in a loop.
• How many times: Up to the length of the shorter string plus one (to check the terminating null character).

How Execution Grows With Input

As the strings get longer, the number of character checks grows roughly with the string length.

Input Size (n)	Approx. Operations
10	Up to 10 character comparisons
100	Up to 100 character comparisons
1000	Up to 1000 character comparisons

Pattern observation: The work grows linearly as the strings get longer.

Final Time Complexity

Time Complexity: O(n)

This means the time to compare grows in a straight line with the length of the strings.

Common Mistake

[X] Wrong: "String comparison always takes the same time no matter the string length."

[OK] Correct: The function checks characters one by one, so longer strings usually take more time.

Interview Connect

Understanding how string comparison time grows helps you write efficient code and explain your reasoning clearly in interviews.

Self-Check

"What if we stopped comparing as soon as we find the first difference? How would the time complexity change in the best case?"