I've been reading Cracking the Coding Interview and at the very beginning I got to the strange statement that the next complexity will be \$O(n^2)\$.
public String makeSentence(String[] words){
String sentence = "";
for (String w:words){
sentence+=w;
}
return sentence;
}
I can't get it. Why is it \$O(n^2)\$? Here I found another article on this topic.
For every call to String.concat(), a new string instance is created. To create that instance, the contents of the previous string needs to be copied to the new one plus the contents of the concatenated string. This is done for every string in the collection. So if you look at in in terms of how many strings are concatenated (and not the characters copied), you're copying the contents of the n strings by the time you reach the nth iteration and all that matters is the worst case (the last iteration). Therefore it has \$O(n^2)\$ performance.
As Jeff points out a new string is created every time you do += on the string.
And thus correctly explains why the complexity is O(2)
The key point is the java.lang.String is not mutable.
Strings are constant; their values cannot be changed after they are created. String buffers support mutable strings. Because String objects are immutable they can be shared.
So any attempt to modify it generated a completely new string (which to programmers in most other languages is strange).
The solution is to use the java.lang.StringBuffer. This behaves like most other languages string object and allows mutation. The objective is to build a string inside a StringBuffer and when you are finally finished covert this into a string.
A thread-safe, mutable sequence of characters. A string buffer is like a String, but can be modified. At any point in time it contains some particular sequence of characters, but the length and content of the sequence can be changed through certain method calls.
StringBuilder should be used over StringBuffer for new code that doesn't need to work under 1.4 JVMs or earlier. "Where possible, it is recommended that this class be used in preference to StringBuffer as it will be faster under most implementations."
\$\endgroup\$
Commented
Aug 9, 2011 at 18:58
StringBuilder should be used here over StringBuffer - The builder itself isn't visible outside the scope of the method, so there isn't any problem regarding threading issues/
\$\endgroup\$
Commented
Aug 9, 2011 at 20:51
Immutability is not really the issue here. It is possible to write a mutable string class where this still would be \$O(n^2)\$ or an immutable string class of lower complexity (Sun could have done the latter anyway). The problem here is that at each iteration, the algorithm is rereading the string from the previous iteration in order to produce a new string.
To reduce it by an order of magnitude, you need to shift references. In some cases, the compiler very well might do this anyway, depending upon the sophistication of code optimization. In the case of the class String however, I think it still does it the expensive way, by design.
StringBuffer may be mutable, but I don't see how that is what makes it more efficient in this case. What matters is that at each iteration, it simply appends a reference to the list of characters instead of reads each item for any reason, whether to copy them into a new string instance as String does in this example, or for some other silly reason. But to focus on this as a mutability/immutability issue I think misses the point.
Simple illustration of what I mean. Input a string of letters. At each iteration, you read the previous string to create a new string, and then the current index of the input string to append to the new string. The general relation is the length of the string produced by the previous iteration plus one, which gives you a complexity of \$n^2 - 1\$, or \$O(n^2)\$.
