Big O for multi loops
Almost always the best way to compute complexities of kinda loops should be done by making use of sigma notation.
P.S. I don't write necessary +1s in the formulas since it is not important for Big-O notation and doesn't affect max power which is 5
.
It looks like it is O(n^5)
.
for (int i = 0; i < n; i++) // 0 to n -> O(n)
for(int j = 0; j < i*i; j++) // 0 to n * n -> O(n^2) repeated n times -> O(n^3)
for (int k = 0; k < j; k++) // 0 to n * n -> O (n^2) repeated O(n^3) times -> O(n^5)
In the best case scenario, three nested loops would give you O(n^3)
, but as you have the second loop repeat (n^2)
times, that will square its complexity and of the third loop as well. So in a simple mathematical notation that will be: (n) * (n * n) * (n * n) = n^5
.