why running time of this code is 0(n^2)

Question

why running time of this code is O(n^2).(as written in cracking the coding interview book).and how it could be improved

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

Copy of [this](http://stackoverflow.com/questions/7156122/what-is-the-complexity-of-this-simple-piece-of-code) — NV Bhargava, Aug 21 '14 at 19:14
I'd say that's O(*n*) where *n* is the total number of characters in `words`. — aioobe, Aug 21 '14 at 19:14
[There are already some really good answers here.](http://stackoverflow.com/questions/7156122/what-is-the-complexity-of-this-simple-piece-of-code) It's a clear duplicate. — But I'm Not A Wrapper Class, Aug 21 '14 at 19:17

score 1 · Answer 1 · answered Aug 21 '14 at 19:15

1

For n = the number of elements in the words array

The for loop means at least O(n)

Inside the for loop, each instance of sentence.append(w) should be "constant" since sentence is a StringBuffer.

Doing constant things n times means you get a total of O(n)

answered Aug 21 '14 at 19:15

Kache

15,647
12
51
79

Again, StringBuffer, so it's not O(n^2). See the proper answer in the linked duplicate. – Pimgd Aug 21 '14 at 19:17
Yeah I answered instinctively, but edited it already. – Kache Aug 21 '14 at 19:19

score 0 · Answer 2 · answered Aug 21 '14 at 19:14

0

The key line to look at is for (String w : words) sentence.append(w);

In Java, a String append is an O(n) operation. Because the append is inside the for loop, the method as a whole is O(n^2).

answered Aug 21 '14 at 19:14

therealrootuser

10,215
7
31
46

Except StringBuffer, so this answer is wrong. – Pimgd Aug 21 '14 at 19:15
1

You're walking about two different *n* :-) – aioobe Aug 21 '14 at 19:15

why running time of this code is 0(n^2)

2 Answers2