title: Space complexity of adding Java Strings char by char
body: <p>When building a Java String char by char through a loop through "addition", it can be observed that the <em>time complexity</em> of performing this operation is poor: it is of <em>quadratic</em> <code>O(n^2)</code> time. However, I am wondering if the space complexity of "adding" a String char-by-char through a loop is also poor.</p>
  
  <p>Here is a minimal example of a program which performs building a String via char-by-char addition with stopwatch timing. The results I got shown below clearly show a quadratic curve:</p>
  
  <pre><code>/**Create a String of n 'A's char-by-char.
   * @param n Number of 'A's to be appended
   * @return The finished string
   */
  public static String appendString(int n) {
      String str = "";
      // Timed run starts here
      long t = System.currentTimeMillis();
      // String concatenation occurs here
      for (int k = 0; k &lt; n; k++)
          str += "A";
      t = System.currentTimeMillis() - t;
      // Timed run ends
      System.out.printf("%d\t%d\n", n, t);
      return str;
  }
  </code></pre>
  
  <p>Although I can get the time complexity of the program, I am wondering what is the <em>space complexity</em> of building a String char-by-char? </p>
  
  <p>A detailed answer that addresses memory management is preferred. (I suspect it is also quadratic because Strings are immutable, and each time you have to allocate new memory for ever-increasing Strings)</p>
  
  <p><strong>Note:</strong> This is not a duplicate of <a href="https://stackoverflow.com/questions/15400508/string-concatenation-complexity-in-c-and-java">String concatenation complexity in C++ and Java</a> because it does not address <em>space complexity</em>. I am specifically asking for a detailed <em>space complexity</em> analysis.</p>