String vs StringBuilder

Why appending to a string in Java can become O(n²).

 🔴 Problem: Strings are immutable in Java

When you do:

String s = "";
s += "a";
s += "b";
s += "c";

Each += operation:

• Creates a new String

• Copies all characters from the old string

• Appends the new character

So, internally it works like this:

Step 1: s = "";             // length = 0
Step 2: s = s + "a";        // copy "" + "a" → O(1)
Step 3: s = s + "b";        // copy "a" + "b" → O(2)
Step 4: s = s + "c";        // copy "ab" + "c" → O(3)
...

If you do this in a loop n times:

String s = "";
for (int i = 0; i < n; i++) {
    s += "a";
}

The cost of each iteration is increasing:

• First iteration: O(1)

• Second: O(2)

• Third: O(3)

• ...

• n-th iteration: O(n)

➡️ Total time = 1 + 2 + 3 + ... + n = O(n²)

---

✅ Solution: Use StringBuilder

StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append("a");
}
String result = sb.toString();

• StringBuilder maintains an internal buffer.

• It grows efficiently without copying the entire string each time.

• Each append() is O(1) amortized, so total time = O(n).

---

🔁 Summary

Method	Time Complexity	Reason
str1 + str2 once	O(n + m)	Copies both strings once.
+= in a loop (String)	O(n²)	Creates a new string each time, copying the full old one.
StringBuilder.append()	O(n)	Uses resizable buffer, appends in constant time amortized.