String time complexity
<pre><code>public String joinWords(String[] words)
{ 
     String sentence = "";
     for (String w : words)
     {
        sentence = sentence + w;  
     }
     return sentence;
}
</code></pre>

<blockquote>
  <p>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).</p>
</blockquote>

<p>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 !   </p>

<p><code>String</code> itself is immutable but reference is not.</p>

<p>Assume next example:</p>

<pre><code>String s = "1";
s = s + "2";
</code></pre>

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

<pre><code>String s = "1";
String sBak = s;
s = s + "2";
</code></pre>

<p><code>s</code> equal to <code>"12"</code> again. And we can check <code>sBak</code> to ensure that <code>"1"</code> did not changes.</p>

<p>Now back to your sample. Assume that <code>words = {"first, "second", "third"}</code>.</p>

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

<p>So length of string referenced by <code>sentence</code> will increase each time (each time <code>sentence</code> will point to different string).</p>

java c# python string data-structures