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
– Adrian Colomitchi, Commented Dec 13, 2016 at 12:20
What abstract machine model/run time environment/programming language? Is sentence = sentence + w; constant effort? — greybeard
– greybeard, Commented Dec 13, 2016 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): stackoverflow.com/q/7156122/6809386 — Alexander Anikin
– Alexander Anikin, Commented Dec 13, 2016 at 15:40

Spektre · Accepted Answer · 2016-12-13 12:32:16Z

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

Community · Accepted Answer · 2020-06-20 09:12:55Z

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, 2020 at 9:12

CommunityBot

11 silver badge

answered Dec 13, 2016 at 12:24

Adrian Colomitchi

3,9921 gold badge16 silver badges23 bronze badges

Collectives™ on Stack Overflow

Time complexity of string build algorithm

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related