Multi tool use

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;
// Timed run ends
System.out.printf("%dt%dn", n, t);
return str;
}


Although I can get the time complexity of the program, I am wondering what is the space complexity of building a String char-by-char?

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)

Note: This is not a duplicate of String concatenation complexity in C++ and Java because it does not address space complexity. I am specifically asking for a detailed space complexity analysis.

2 Answers
2

It uses quadratic space. Or, rather, a quadratic amount of space is allocated, because each iteration of the loop will (at least in code which the JIT doesn't do something clever with) allocate a new char array:

new char[1]
new char[2]
new char[3]
// Etc.


The reason for the quadratic time performance is copying the strings into these ever-larger arrays.

2n+1

new char[1]

new char[2]

new char[3]

Your code is quite inefficient, because there is an implicit StringBuilder being created to add a single character in your loop. This,

StringBuilder

for (int k = 0; k < n; k++)
str += "A";


is equivalent to something like

for (int k = 0; k < n; k++)
str = new StringBuilder(str).append("A").toString();


You could greatly improve space (and time) performance by using a single StringBuilder instead (and you can explicitly size it). Like,

StringBuilder

StringBuilder sb = new StringBuilder(n);
for (int k = 0; k < n; k++)
sb.append("A");
String str = sb.toString();


Or, in Java 8+, you could use a generator and limit it to n times and collect that. Like,

n

return Stream.generate(() -> "A").limit(n).collect(Collectors.joining());


char cs = new char[n]; Arrays.fill(cs, 'A'); String str = new String(cs);

O(n)

O(log n)

A

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.