Time complexity of string build algorithm

Question

String joinWords (String[] words){
   String sentence = "";
   for(String w: words){
     sentence = sentence + w;
   }
  return sentence;
}

The book reports this to be O(xn^2)

Here is my working:

1 call to create String sentence originally

There are N calls (due to N calls for the for loop)

then there are N calls to assign sentence = sentence + w

Last call to send return sentence;

Total:

Which gives O(N^2 + 2) = O(N^2)

Questions (1) Is my working correct?

(2) Where do they get the extra factor of x in O(xn^2)?

Thanks!

"then there are N calls to assign sentence = sentence + w" true, but why would those N need to be multiplied with another N? — Adrian Colomitchi, Dec 13 '16 at 12:20
What abstract machine model/run time environment/programming language? Is `sentence = sentence + w;` constant effort? — greybeard, Dec 13 '16 at 12:34
x is average length of word, but time complexity is O((xn)^2). It can be optimized by StringBuilder to O(xn): http://stackoverflow.com/q/7156122/6809386 — Alexander Anikin, Dec 13 '16 at 15:40

score 1 · Answer 1 · answered Dec 13 '16 at 12:32

that is poorly written example because it will reallocate the sentence N times instead of once causing the O(x.N^2)

String sentence = "";
for(String w: words) // this loops N times (if N is number of words)
 sentence = sentence + w; // this reallocates the whole thing

If sentence = sentence + w; would be O(1) then the result will be O(N) but that is not the case because:

 sentence = sentence + w;

is in reality something like this:

String temp = new string of size (sentence.size + w.size);
for (i=0;i<sentence.size;i++) temp[i]=sentence[i];
for (i=0;i<w.size;i++) temp[i+sentence.size]=w[i];
sentence=temp; // just pointer assignment O(1)
delete temp;

Which is O(M) where Mis the number of letters in resulting sentence which is x.N on average (x is average number of letters per word).

So the final complexity is O(x.N^2) (not taking into account amortization) while it could be just O(x.N) if would use preallocation step ...

score 0 · Answer 2 · edited Jun 20 '20 at 09:12

0

Total:

Which gives O(N^2 + 2) = O(N^2)

Put your cycle like this:

String joinWords (String[] words){
   String sentence = "";
   // words.length is a constant, no calls are made
   for(int i=0; i<words.length; i++){
     sentence = sentence + w;
   }
  return sentence;
}

While sentence = sentence + w; is indeed "data manipulation" where does your other N in the alleged O(N^2) comes from?

edited Jun 20 '20 at 09:12

Community

1
1

answered Dec 13 '16 at 12:24

Adrian Colomitchi

3,974
1
14
23

Time complexity of string build algorithm

2 Answers2