Cost of string concatenation

Question

What is the cost of the following method. How do you calculate it?

public String joinWords(String[] words) {
    String sentence = "";
    for (String w : words) {
        sentence = sentence + word;
    }
    return sentence;
}

Answer 1

The runtime is O(mn), where n is the total number of characters in the input strings and m is the number of input strings.

To see this, remember that in Java, string concatenation runs in time O(r + s), where r and s are the lengths of the strings being concatenated together. Therefore, if the string lengths are n1, n2, ..., n_m, then the runtime will be

n1 + (n1 + n2) + (n1 + n2 + n3) + ... + (n1 + n2 + ... + n_m)

= m(n_1) + (m - 1)(n_2) + (m - 2)(n-3) + ... + n_m

= m(n_1 + n_2 + ... + n_m) - n_2 - 2n_3 - 3n_4 - ... - (m - 1)n_m

Subject to the constraint that n_1 + ... + n_m = n, this is maximized when n_1 = n and all the other values are 0. In that case, the runtime becomes mn, so the runtime is O(mn).

Hope this helps!