Big O Theory- triple nested loop

Question

If I have a function of:

for(i=0;i<n;i++)
   for(j=0;j<i*i;j++)
      for(k=0;k<j;k++)
         System.out.println(k);

Would the big O of this function be n^5 from having: n*((n-1)^2)*((n-1)^2)-1?

Answer 1

Your function is O(1) because it returns the first k, the loop ends at first iteration. Assuming it don't return immediately, it is n^5 as you thought.

​​ For each i the second loop is looping i^2 times, and the third loop is going j times. So for each i it is looping i^4 times. So the total is Sum(i^4) (1..n) which is O(n^5).