Сложность времени заданного кода?

Question

что временная сложность этого кода:

for (i=1 to n) 
    for (j=1 to i^2) 
     if ((j mod i)==0) 
       for (k=1 to j) 
        write ("*"); 

Я нахожу это соотношение между I, J и К: , например, п = 4, так:

i  j    k 
1  1-1   1 k run for 1time 
2  1-4   1,2,3,4 k run for 2 and 4 times 
3  1-9   1,2,3,4,5,6,7,8,9 k run for 3, 6 and 9 times 
4  1-16   1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 k run for 4, 8, 12 and 16 times 

, но я не могу найти его сложность

Answer 1

Возникновение j mod i = 0 можно считать пренебрежимо малым по сравнению с большим значением n. для 1-го двух вложенных циклов, очевидно, сложность суммирования pow (i, 2) от 1 до n. поэтому мы можем взять сложность как O (n^3).