What is the complexity of this simple piece of code?

Question

I'm pasting this text from an ebook I have. It says the complexity if O(n²) and also gives an explanation for it, but I fail to see how.

Question: What is the running time of this code?

public String makeSentence(String[] words) {     StringBuffer sentence = new StringBuffer();     for (String w : words) sentence.append(w);     return sentence.toString(); } 

The answer the book gave:

O(n²), where n is the number of letters in sentence. Here’s why: each time you append a string to sentence, you create a copy of sentence and run through all the letters in sentence to copy them over If you have to iterate through up to n characters each time in the loop, and you’re looping at least n times, that gives you an O(n²) run time. Ouch!

Can someone please explain this answer more clearly?

Answer 1

This seems to be a question of mislead, because I happened to read that book just now. This part of text in the book is a typo! Here is the context:

===================================================================

Question: What is the running time of this code?

1 public String makeSentence(String[] words) { 2 StringBuffer sentence = new StringBuffer(); 3 for (String w : words) sentence.append(w); 4 return sentence.toString(); 5 } 

Answer: O(n²), where n is the number of letters in sentence. Here’s why: each time you append a string to sentence, you create a copy of sentence and run through all the letters in sentence to copy them over. If you have to iterate through up to n characters each time in the loop, and you’re looping at least n times, that gives you an O(n²) run time. Ouch! With StringBuffer (or StringBuilder) can help you avoid this problem.

1 public String makeSentence(String[] words) { 2 StringBuffer sentence = new StringBuffer(); 3 for (String w : words) sentence.append(w); 4 return sentence.toString(); 5 } 

=====================================================================

Have you noticed that the author messed it up? The O(n²) solution she mentioned (the first one) was exactly the same as the 'optimized' one (the latter). So, my conclusion is that the author was trying to render something else, such as always copying the old sentence to a new buffer when appending every next string, as the example of an O(n²) algorithm. StringBuffer should not be so silly, as the author also mentioned 'With StringBuffer (or StringBuilder) can help you avoid this problem'.