Попытка вычислить временную сложность следующего фрагмента кода

Question

Является ли временная сложность следующего фрагмента кода O(n^5)? Я рассуждаю так: внешнее значение для l oop равно O(n), среднее для l oop равно O(n^2), поскольку значение i основано на значении n, а внутреннее для l oop равно O(n^2), поскольку значение j основано на значении if i ^ 2, которое основано на значении n ^ 2.

int x = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i * i; j++) {
        for (int k = 0; k < j; k++) {
            x++;
        }
    }
}

Answer 1

Это не так просто. Чтобы определить сложность, нужно рассчитать, во сколько раз увеличится x.

The most inner loop runs `j` times.
The middle loop runs `i*i` times.
The outer loop runs n times.

Давайте уменьшим:

Средняя сложность l oop равна:

1+2+3+...+(i-1)+i+(i+1)+...+(i-1)*(i-1) = (i^2-2i+1)*i*i/2=(i^4-2i^3+i^2)/2

И внешний l oop запускается n раз для каждого n от 0 до n-1. Он суммирует до:

n^5/10 - n^4/2 + 5n^3/6 - n^2/2 + n/15

и на самом деле это O(n^5).

Математическая запись: