Space complexity of adding Java Strings char by char
Space complexity of adding Java Strings char by char When we have to build a Java String char by char through a loop through "addition", it can be observed that the time complexity of performing this operation is poor: it is of quadratic O(n^2) time. However, I am wondering if the space complexity of "adding" a String char-by-char through a loop is also poor. O(n^2) 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: /**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 < n; k++) str += "A"; t = System.currentTimeMillis() - t; ...