Сложность времени, когда внутренний цикл начинается с j = 2

Question

Я получаю O(n^2 logn) как вывод следующего кода. И все же я не могу понять, почему?

int unknown(int n) {
    int i, j, k = 0;
    for (i = n / 2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n / 2;
    return k;
}

Answer 1

Фиксированная постоянная начальная точка не будет иметь никакого значения для внутреннего цикла с точки зрения сложности.

Начиная с двух вместо одного, будет означать на одну итерацию меньше, но отношение все ещелогарифмический.

Подумайте о том, что происходит, когда вы удваиваете n.Это добавляет еще одну итерацию в этот цикл независимо от того, начинаете ли вы с одного или двух.Следовательно, это O(log N) сложность.

Однако вы должны иметь в виду, что внешний цикл - это O(N) один, так как количество итераций пропорционально N.Это делает функцию в целом O(N log N), а не O(N<sup>2</sup> log N), которую вы устанавливаете.