Time Complexity: String comparison and equality
O(n)
0
0
String comparison and equality in C Sharp (C#) - Time & Space Complexity
Understanding Time Complexity
When comparing two strings, the time it takes depends on their length and content.
We want to know how the work grows as strings get longer.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
string s1 = "hello world";
string s2 = "hello there";
bool areEqual = s1.Equals(s2);
This code checks if two strings are exactly the same.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Comparing characters one by one in both strings.
- How many times: Up to the length of the shorter string, or until a difference is found.
How Execution Grows With Input
As strings get longer, the comparison checks more characters.
| 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 roughly in direct proportion to the string length.
Final Time Complexity
Time Complexity: O(n)
This means the time to compare grows linearly with the length of the strings.
Common Mistake
[X] Wrong: "Comparing two strings always takes the same time regardless of their content."
[OK] Correct: The comparison stops early if a difference is found, so shorter matches can be faster.
Interview Connect
Understanding how string comparison scales helps you reason about performance in many programs.
Self-Check
"What if we compare strings ignoring case? How would the time complexity change?"