I read on several manuals and online sources that the running time of "simple string concatenation" is O(n^2)?
The algorithm is this: we take the first 2 strings, create a new string, copy the characters of the 2 original strings in the new string, and repeat this process over and over again until all strings are concatenated. We are not using StringBuilder or similar implementations: just a simple string concatenation.
I think the running time should be something like O(kn) where k = number of strings, n = total number of characters. You don't copy the same characters n times, but k times, so it should not be O(n^2). For example, if you have 2 strings, it's just O(n). Basically it's n + (n-x) + (n-y) + (n-z)... but k times, not n times.
Where am I wrong?
StringBuilder
. Well, prior to StringBuilder it usedStringBuffer
which works the same way except for synchronization so you can use it in concurrent applications. That has been there since Java 1.0. So there is not other way to evaluate concatenation for Java unless you enquire about the efficiency of a particular algorithm.