Time Complexity: String immutability
O(n^2)
0
0
String immutability in Java - Time & Space Complexity
Understanding Time Complexity
We want to understand how working with strings in Java affects the time it takes to run code.
Specifically, how does changing strings impact performance as the string size grows?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
String s = "";
for (int i = 0; i < n; i++) {
s = s + "a";
}
This code builds a string by adding one character at a time inside a loop.
Identify Repeating Operations
- Primary operation: Adding a character to the string inside the loop.
- How many times: The loop runs n times, repeating the addition each time.
How Execution Grows With Input
Each time we add a character, Java creates a new string by copying the old one and adding the new character.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 55 copies (1+2+...+10) |
| 100 | About 5,050 copies |
| 1000 | About 500,500 copies |
Pattern observation: The work grows much faster than the input size; it grows roughly like the square of n.
Final Time Complexity
Time Complexity: O(n2)
This means the time to build the string grows very quickly as the string gets longer, because each addition copies the whole string again.
Common Mistake
[X] Wrong: "Adding characters to a string in a loop takes time proportional to the number of characters only."
[OK] Correct: Because strings are immutable, each addition copies the entire string so far, making the total work much larger than just n.
Interview Connect
Understanding how string immutability affects performance helps you write better code and explain your choices clearly in interviews.
Self-Check
What if we used a StringBuilder instead of adding strings directly? How would the time complexity change?