Как сложность времени O (N ^ 2) здесь?

Question

Я уже знаю, что ответ на этот вопрос O(N^2), но я не могу понять, как.Я знаю, что цикл for выполняется N раза, но как он может выполняться N^2 раза?

public static String rev(String s) {
    String r = "";
    int N = s.length();
    for (int i = 0; i < N; i++) {
        r = s.charAt(i) + r;
    }
    return r;
}

Answer 1

В Java String конкатенация r = s.charAt(i) + r в цикле равна O(N^2), поскольку Strings неизменны - новая копия String создается при каждой конкатенации.