Почему вычислительная сложность O(n^4)? ⇐ JAVA

[Anonymous]

Код: Выделить всё

int sum = 0;
for(int i = 1; i < n; i++) {
for(int j = 1; j < i * i; j++) {
if(j % i == 0) {
for(int k = 0; k < j; k++) {
sum++;
}
}
}
}

Я не понимаю, как, когда j = i, 2i, 3i... последний цикл for выполняется n раз. Наверное, я просто не понимаю, как мы пришли к такому выводу на основе оператора if.

Изменить: я знаю, как вычислить сложность для всех циклов, за исключением того, почему последний цикл выполняется i раз на основе оператора mod... Я просто не знаю посмотреть, как там я. По сути, почему j % i не может подняться до i * i, а не до i?

Подробнее здесь: https://stackoverflow.com/questions/601 ... lexity-on4