Questions
8 of 19
Why is string concatenation in a loop O(n²)? How do you fix it? (StringBuilder)
Difficulty: 3/10
Efficient String Construction
Repeated concatenation of immutable strings inside a loop can become O(n²) because each concatenation may allocate a new string and copy the existing contents. As the accumulated string grows, the amount of copying grows as well.
javascript
- 1
Immutable strings cannot be modified in place.
- 2
Repeated concatenation may create many temporary objects.
- 3
The cumulative copying can become quadratic for a growing result.
- 4
StringBuilder maintains a mutable buffer and grows its capacity as needed.
- 5
With suitable capacity management, StringBuilder typically provides near-linear total construction time.
Follow-up Questions
- What is the complexity of StringBuilder append?
- When is simple string concatenation acceptable?