j is depend upon i and k is depend upon i and j ===> we have to unroll the dependency
when i=1
j=1 ===> k=1
when i=2
j=1 ===> k didn't run
j=2 ===> k run 2 times
j=3 ===> k didn't run
j=4 ===> k run 4 times
∴ 2+4 == 2(1+2)
when i=3
j=1 ===> k didn't run
j=2 ===> k didn't run
j=3 ===> k run 3 times
j=4 ===> k didn't run
j=5 ===> k didn't run
j=6 ===> k run 6 times
j=7 ===> k didn't run
j=8 ===> k didn't run
j=9 ===> k run 9 times
∴ 3+6+9 == 3(1+2+3)
.......
when i=p
j=1 ===> k didn't run
j=2 ===> k didn't run ......
j=p ===> k run p times
j=p+1 ===> k didn't run
j=p+2 ===> k didn't run .............
j=2p ===> k run 2p times
j=2p+1 ===> k didn't run
j=3p ===> k run 3p times ..............
j=p*p ===> k run p*p times
∴ p+2p+3p+......+p2 == p(1+2+3+....+p)
Total = 1 ( 1 ) + 2 . ( 1+2 ) + 3. ( 1+2+3 ) + ......+ p . ( 1+2+3+....+p ) +....... + n . ( 1+2+....+n )
from these observations we can conclude that
Time complexity = $\LARGE \sum_{i=1}^{n} ( i$$\sum_{j=1}^{i} j \LARGE) $
= $\LARGE \sum_{i=1}^{n} ( i$ ( 1+2+3+...i )$ \LARGE) $
= $\LARGE \sum_{i=1}^{n} ( i$ $( \frac{i(i+1)}{2} $ $ \LARGE) $
= $\frac{1}{2}\LARGE \sum_{i=1}^{n} ( i^{3} + i^{2} $ $ \LARGE) $
= O(n4)
note that summation of first n natural cubes =$ {( \frac{n(n+1)}{2}) }^{2}$