CODEWITHSUNDEEP
javac#pythonstringdata-structures
Vasili Anoshin
Vasili Anoshin

Reputation: 95

String time complexity

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

Assume that the strings are all the same length (call this x) and that there are n strings. On each concatenation,a new copy of the string is created, and the two strings are copied over,character by character. The 1st iteration requires us to copy x characters. The second iteration requires copying 2x characters. The third iteration requires 3x ,and so on. The total time therefore is O(x + 2x + . . . + nx). This reduces to O(xn^2).

1) I can't understand from the book answer how they get 3x characters in the third iteration , 4x in the 4th iteration . String is immutable and in each sentence variable assignment new String object is created . And then is should copy the previous value of the string char by char and the value of w . And i get 2x characters again . Thank you all !

Upvotes: 2

Views: 2634

Answers (2)

talex
talex

Reputation: 20544

String itself is immutable but reference is not.

Assume next example:

String s = "1";
s = s + "2";

s will contains value "12", but string "1" will not changes. We can check it in next example:

String s = "1";
String sBak = s;
s = s + "2";

s equal to "12" again. And we can check sBak to ensure that "1" did not changes.

Now back to your sample. Assume that words = {"first, "second", "third"}.

Statement sentence = sentence + w; updates sentence variable. After first iteration it will be "" + "first" wich is "first". After second iteration it will be equal to "first" + "second" and so on.

So length of string referenced by sentence will increase each time (each time sentence will point to different string).

Upvotes: 2

Eran
Eran

Reputation: 393986

In the 1st iteration sentence has 0 characters and w has x characters, so you have to copy x characters.

In the 2nd iteration sentence has x characters and w has x characters, so you have to copy 2*x characters.

In the 3rd iteration sentence has 2*x characters and w has x characters, so you have to copy 3*x characters.

In the 4th iteration sentence has 3*x characters and w has x characters, so you have to copy 4*x characters.

And so on...

Upvotes: 7

Related Questions