What is the complexity of this simple piece of cod

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

Looks like O(n) to me (with n being the total number of letters in all the words). You're basically iterating over every character in words to append it into the StringBuffer.

The only way I could see this as being O(n^2) is if append() iterates all the contents in the buffer before appending any new characters. And it may actually do this occasionally if the number of characters exceeds the currently allocated buffer length (it has to allocate a new buffer, and then copy everything from the current buffer into the new buffer). But it won't happen on every iteration, so you still won't have O(n^2).

At most you'd have O(m * n), where m is the number of times the buffer length is increased. And because the StringBuffer will double its buffer size every time it allocates a larger buffer we can determine that m is roughly equal to log2(n) (actually log2(n) - log2(16), since the default initial buffer size is 16 instead of 1).

So the real answer is that the book's example is O(n log n), and that you can get it down to O(n) by preallocating a StringBuffer with a capacity large enough to hold all of your letters.

Note that in Java appending to a string using += does exhibit the inefficient behavior described in the book's explanation, as it has to allocate a new string and copy all the data from both strings into it. So if you do this, it is O(n^2):

String sentence = "";
for (String w : words) {
    sentence += w;
}

But using StringBuffer should not generate the same behavior as in the above example. That's kind of one of the major reasons for StringBuffer to exist in the first place.

Answer 2

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'.

Answer 3

I think these text in the book must be a typo ,I think the right content is below,I fix it:

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

Question: What is the running time of this code?

public String makeSentence(String[] words) {
    String sentence = new String("");
    for (String w : words) sentence+=W;
    return sentence;
}

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.

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

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

Am i right?

Answer 4

That really depends on the implementation of StringBuffer. Supposing .append() was constant time, it's clear that you have an O(n) algorithm in time where n = length of the words array. If .append isn't constant time, you'll need to multiple your O(n) by the time complexity of the method. If indeed the current implementation of StringBuffer copies strings character-by-character, then the algorithm above is

Θ(n*m), or O(n*m), where n is the number of words and m is average word length, and your book is wrong. I assume you're looking for a strict bound.

Simple example that the book's answer is incorrect: String[] words = ['alphabet'] By the book's definition, n=8, so the algorithm will be bounded by 64 steps. Is this the case? Clearly not strictly. I see 1 assignment and 1 copy operation with n characters, so you get about 9 steps. This sort of behavior is predicted by the bounds of O(n*m), as I illustrated above.

I did some digging, and this clearly isn't a simple character copy. It looks like memory is being copied in bulk, which puts us back at O(n), your first guess at the solution.

/* StringBuffer is just a proxy */
public AbstractStringBuilder append(String str) 
{
        if (str == null) str = "null";
        int len = str.length();
        ensureCapacityInternal(count + len);
        str.getChars(0, len, value, count);
        count += len;
        return this;
}

/* java.lang.String */
void getChars(char dst[], int dstBegin) {
             System.arraycopy(value, offset, dst, dstBegin, count);
}

Your book is either old, terrible, or both. I'm not determined enough to dig through JDK versions to find a less optimal implementation of StringBuffer, but perhaps one exists.