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>In the 1st iteration <code>sentence</code> has 0 characters and <code>w</code> has x characters, so you have to copy x characters.</p>

<p>In the 2nd iteration <code>sentence</code> has x characters and <code>w</code> has x characters, so you have to copy 2*x characters.</p>

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

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

<p>And so on...</p>

java c# python string data-structures