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?

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

Solution 2

It's a bit difficult to answer a question about the complexity of this code when it is written at a high level which abstracts away the details of the implementation. The Java documentation doesn't seem to give any guarantees in terms of the complexity of the append function. As others have pointed out, the StringBuffer class can (and should) be written so that the complexity of appending strings does not depend on the current length of the string held in StringBuffer.

However, I suspect it is not that helpful to the person asking this question to simply say "your book is wrong!" - instead, let us see what assumptions are being made and make clear what the author was trying to say.

You can make the following assumptions:

1. Creating a new StringBuffer is O(1)
2. Getting the next string w in words is O(1)
3. Returning sentence.toString is at most O(n).

The question is really what is the order of sentence.append(w), and that depends on how it happens inside the StringBuffer. The naive way is to do it like Shlemiel the Painter.

The silly way

Suppose you use a C-style null-terminated string for the contents of StringBuffer. The way you find the end of such a string is by reading each character, one by one, until you find the null character - then to append a new string S, you can start copying characters from S to the StringBuffer string (finishing with another null character). If you write append this way, it is O(a + b), where a is the number of characters currently in the StringBuffer, and b is the number of characters in the new word. If you loop over an array of words, and each time you have to read all the characters you just appended before appending the new word, then the complexity of the loop is O(n^2), where n is the total number of characters in all the words (also the number of characters in the final sentence).

A better way

On the other hand, suppose that the contents of StringBuffer is still an array of characters, but we also store an integer size which tells us how long the string is (number of characters). Now we no longer have to read every character in the StringBuffer in order to find the end of the string; we can just look up index size in the array, which is O(1) instead of O(a). Then the append function now only depends on the number of characters being appended, O(b). In this case the complexity of the loop is O(n), where n is the total number of characters in all the words.

...We're not done yet!

Finally, there's one more aspect of the implementation that hasn't been covered yet, and that is the one actually brought up by the answer in the textbook - memory allocation. Each time you want to write more characters to your StringBuffer, you're not guaranteed to have enough space in your character array to actually fit the new word in. If there isn't enough space, your computer needs to first allocate some more room in a clean section of memory, and then copy all the information in the old StringBuffer array across, and then it can continue as before. Copying data like this will take O(a) time (where a is the number of characters to be copied).

In the worst case, you have to allocate more memory every time you add a new word. This basically takes us back to square one where the loop has O(n^2) complexity, and is what the book seems to suggest. If you assume that nothing crazy is happening (the words aren't getting longer at an exponential rate!), then you can probably reduce the number of memory allocations to something more like O(log(n)) by having the allocated memory grow exponentially. If that's the number of memory allocations, and memory allocations in general are O(a), then the total complexity attributed just to memory management in the loop is O(n log(n)). Since the appending work is O(n) and less than the complexity of the memory management, the total complexity of the function is O(n log(n)).

Again, the Java documentation doesn't help us in terms of how the capacity of the StringBuffer grows, it just says "If the internal buffer overflows, it is automatically made larger". Depending on how it happens, you could end up with either O(n^2) or O(n log(n)) overall.

As an exercise left to the reader: Find an easy way to modify the function so that the overall complexity is O(n), by removing memory reallocation issues.

Solution 3

The accepted answer is just wrong. StringBuffer has amortized O(1) append, so n appends will be O(n).

If it wasn't O(1) append, StringBuffer would have no reason to exist, since writing that loop with plain String concatenation would be O(n^2) as well!

Solution 4

I tried to check it using this program

public class Test {

    private static String[] create(int n) {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = "abcdefghijklmnopqrst";
        }
        return res;
    }
    private static String makeSentence(String[] words) {
        StringBuffer sentence = new StringBuffer();
        for (String w : words) sentence.append(w);
        return sentence.toString();
    }


    public static void main(String[] args) {
        String[] ar = create(Integer.parseInt(args[0]));
        long begin = System.currentTimeMillis();
        String res = makeSentence(ar);
        System.out.println(System.currentTimeMillis() - begin);
    }
}

And result was, as expected, O(n):

java Test 200000 - 128 ms

java Test 500000 - 370 ms

java Test 1000000 - 698 ms

Version 1.6.0.21

Solution 5

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?

View more solutions

Comments

[Vineet Reynolds]

The Sun/Oracle JVM (Hotspot) implements the append operation using System.arraycopy which in turn relies on a O(n) operation (implemented in objArrayKlass.cpp of the OpenJDK distribution) to perform the actual copying of array object members in memory. So, O(M*n) is correct. I doubt any other JVM does copying in constant time, given that occupied memory blocks have to be realigned.

[Stefan Kendall]

Is System.arraycopy necessarily serial on all JVMs? I could imagine that somehow being optimized for super-concurrent hardware that made this nearly linear for most sizes of a given string.

[Stefan Kendall]

@Vineet: Ah. Well, how about an implementation which increases the length of the buffer while deferring the actual copy of memory? I guess the real answer here is that the implementation of StringBuffer is entirely the solution to this question, and that can and likely will vary over time and across JVM implementations.

[Vineet Reynolds]

the problem with resizing/copying the array, is that the actual implementation varies from one architecture to another (assuming only char arrays here, for the sake of brevity). On Windows and SPARC, it appears to be O(n) as there is atleast one loop that iterates through the number of the characters being copied. On the Linux and the Solaris x86 platforms, the JVM delegates to the extern C calls (of whose characteristics I'm not aware; I'm having quite a struggle with assembly language).

[aroth]

@Vineet - It's safe to assume that copying data from one buffer to another is O(n). At least until someone demonstrates an algorithm that can do faster. I think at best some architectures might include special instructions that allow the copying of some fixed multiple of words as part of a single operation. But even with such an instruction, the copy operation still reduces to O(n).

[Vineet Reynolds]

@aroth, yes, that's my point. Given all other checks that are implemented in the JVM, array copying tends to be O(n). Constant-time copies appears to be near impossible, as the best possibilities are memcpy/memmove which are again O(n), although OpenJDK appears to use these for primitives and not for object arrays.

[Mechanical snail]

Note that javac actually optimizes string concatenation to use StringBuilders.

[fgb]

The complexity is O(n) even with the reallocations. Multiplying log(n) by n is misleading because not every reallocation has the same cost. The final reallocation has about the same cost as all the others put together.

[LionC]

If you think that the content of the original question is wrong in any way edit it

[Jared Burrows]

I believe the book meant to say this as well.

[Kirill Vashilo]

Right, the mistake has been corrected in the next book's edition

[sbhatla]

What is the complexity? Your answer did not say that.

[sbhatla]

Cna you cite the source for the complexity?

[ebyrob]

I think of the memory performance as: O(log(n) * log(n)) though I'm not sure if that's a helpful way of thinking of amortization. It does remind me it could be close to O(n) and bears more looking into. In this case, you're copying an avg of roughly log(n) characters roughly log(n) times.

[rogerdpack]

Ahh StringBuffer underneath basically copies everything to a single byte array, which "doubles" in size when its size is expanded, so hence the amortized O(1). Gotcha.

[Nagabhushan Baddi]

You are wrong. With the complexity would be n^3. Since, the complexity would be n+2n+...n^2 which is proportional to n^3.