If I have a function of: <pre class="prettyprint"><code>for(i=0;i<n;i++) for(j=0;j<i*i;j++) for(k=0;k<j;k++) System.out.println(k); </code></pre> Would the <code>big O</code> of this function be <code>n^5</code> from having: <code>n*((n-1)^2)*((n-1)^2)-1</code>?

Your function is <code>O(1)</code> because it returns the first <code>k</code>, 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 <code>i^2</code> times, and the third loop is going <code>j</code> times. So for each <code>i</code> it is looping <code>i^4</code> times. So the total is <code>Sum(i^4) (1..n)</code> which is <code>O(n^5)</code>.

Big O Theory- triple nested loop

Tags:

big-o

nested-loops

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?

967

asked Jan 28 '14 03:01

Danny2036

1 Answers

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).

187