String comparison (equals, compareTo) in Kotlin - Time & Space Complexity

Time Complexity: String comparison (equals, compareTo)

O(n)

Understanding Time Complexity

When we compare two strings in Kotlin, the time it takes depends on their length.

We want to know how the work grows as the strings get longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

val str1 = "hello"
val str2 = "world"

// Check if strings are equal
val areEqual = str1.equals(str2)

// Compare strings lexicographically
val comparison = str1.compareTo(str2)
    

This code checks if two strings are the same and then compares their order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing characters one by one in the strings.
• How many times: Up to the length of the shorter string, until a difference is found or end is reached.

How Execution Grows With Input

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

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 with the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to compare strings grows in a straight line as the strings get longer.

Common Mistake

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

[OK] Correct: The program 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 answer questions clearly.

Self-Check

"What if we compare strings that are always different in the first character? How would the time complexity change?"