String manipulation complexity 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.