title: Why is the complexity of simple string concatenation O(n^2)?
body: <p>I read on several manuals and online sources that the running time of "simple string concatenation" is O(n^2)?</p>
  
  <p>The algorithm is this: we take the first 2 strings, create a new string, copy the characters of the 2 original strings in the new string, and repeat this process over and over again until all strings are concatenated. We are not using StringBuilder or similar implementations: just a simple string concatenation.</p>
  
  <p>I think the running time should be something like O(kn) where k = number of strings, n = total number of characters.
  You don't copy the same characters n times, but k times, so it should not be O(n^2). For example, if you have 2 strings, it's just O(n).
  Basically it's n + (n-x) + (n-y) + (n-z)... but k times, not n times.</p>
  
  <p>Where am I wrong?</p>