Time Complexity: String comparison
O(n)
0
0
String comparison in Java - Time & Space Complexity
Understanding Time Complexity
When we compare two strings, the time it takes depends on their length. We want to understand how this time grows as the strings get longer.
How does the number of steps change when comparing bigger strings?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
public boolean compareStrings(String a, String b) {
if (a.length() != b.length()) {
return false;
}
for (int i = 0; i < a.length(); i++) {
if (a.charAt(i) != b.charAt(i)) {
return false;
}
}
return true;
}
This code checks if two strings are exactly the same by comparing each character one by one.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Loop comparing characters at each position.
- How many times: Up to the length of the strings (n times).
How Execution Grows With Input
As the strings get longer, the number of character comparisons grows roughly the same as the string length.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | Up to 10 character checks |
| 100 | Up to 100 character checks |
| 1000 | Up to 1000 character checks |
Pattern observation: The work grows in a straight line with the string length.
Final Time Complexity
Time Complexity: O(n)
This means the time to compare two strings grows directly with their length.
Common Mistake
[X] Wrong: "Comparing two strings always takes the same time regardless of their length."
[OK] Correct: The comparison checks each character until a difference is found or the end is reached, 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 used a method that compares only the first few characters? How would the time complexity change?"