Note: i runs from 0 to n-1 , j run from i to i^2 – 1 and k from 0 to j-1
So, For i=0 and 1 , j will not run at all.
For i=2, j from 2 to 3 but will enter if statement only for j=2 so k runs from 0 to 1…... [2 times]
For i=3, j from 3 to 8 but if statement valid for only j=3,6 so k runs from 0 to 2(for j=3) and 0 to 5 (for j=6) ……..[(3+6) times= 3*(1+2) times]
so if you look at the pattern ….
For i=4 …….. [4*(1+2+3) times]
For i=5 ……...[5*(1+2+3+4) times]….. and so on
Total time = 2*1 + 3*(1+2) + 4*(1+2+3) + 5*(1+2+3+4) +……….. ….+ (n-1)*(1 + 2 + 3 +…….+ n-2 )
= ∑(j=2 to n-1) [j * ∑(k=1 to j-1) k]
= ∑(j=2 to n-1)[ j*(j-1)*j/2] …………. let m=(j-1)
= ½ ∑(m=1 to n-2) [ m*(m+1)^2 ]
= ½ ∑(m=1 to n-2)[ m^3 + 2m^2 + m ]
= ½ [ ((n-2)*(n-1)/2)^2 + 2*(n-2)*(n-1)*(2n-3)/6 + (n-2)*(n-1)/2]
=> O(n^4)