String Concatenation Complexity in Java

Question

I'm having trouble why a string concatenation in Java has an O(N) run-time. Can someone explain why this is so, and whether using the StringBuilder class has the same complexity?

Answer 1

Because it takes (on average) time linearly proportional to the number of characters in two string(s) to concatenate them in Java. As String concatenation performed like "a" + "b" already uses StringBuilder, I think it's safe to say that is also O(N). Remember, Java String is immutable.

Answer 2

Every time you concat a string a new buffer is created and the contents are copied over. Strings are immutable in Java.

The StringBuilder/StringBuffer uses an internal buffer and only creates an immutable string when you call toString(). Less copying and allocating results in faster code. The only time copying and allocating occur is when the internal buffer runs out; You have control over that buffer size as well.

Now, to make things more confusing, some Java based languages know if a string can be optimized, and create a string buffer behind the scenes, so you don't really benefit from using the buffer based classes.