Here's the code for orderedInsertion for an array:

    public void orderedInsert(int x){
    int i =0;
    for(i=0;i<count;i++) if(arr[i]>x) break;
    for(int j=count-1;j>=i;j--) arr[j+1] = arr[j];

If instead of using a break right after the IF statement, I did implement the second for loop ( the one with j variable immediately as follows: EDITED CODE:

    public void orderedInsert(int x) {
        boolean flag = false;
        int i =0;
            if (arr[i]>x) {
                    arr[j+1] = arr[j];
                    arr[i] = x;
                    flag = true;
                if (flag) 

Would both algorithms run in O(N)? This is what makes sense to me, but my instructor said "if you see two nested loops, this means it runs O(N^2).

What makes sense to me is that even in the worst case scenario we will only traverse N times.

  • You are right. In most code with nested loops, the outer loop executes a certain number of times, and the inner loop will also execute a certain number of times each time the outer loop executes, so that the number times will be O(N^2) or O(M*N). In this case, though, you get to the inner for only once--not once for each execution of the outer loop. So what your instructor said does not apply in this case. P.S. You don't need flag--you can just break from inside the if. – ajb Oct 9 '14 at 21:25
  • PPS. Indenting your code properly would be a big help for readers (and your instructor) to see what's going on. – ajb Oct 9 '14 at 21:26
  • Your code in the rewritten method (2nd block) has 2 open braces { but 3 close braces }, and with the current bracing your if(flag)break; is not within a loop, so does nothing. – Stephen P Oct 9 '14 at 21:35
  • I didn't notice that--apparently the code is missing a {. So the actual code appears to be O(N^2) (and probably doesn't work right at all), but the intended code should be O(N). (Or perhaps we should say the actual code is O(1) because it won't compile.) I think I read the code the way you meant it, as opposed to the way it was incorrectly written. – ajb Oct 9 '14 at 23:41
  • I've updated the code in OP. It was a quick edit I did without writing in eclipse, sorry about that. – Lifter Oct 10 '14 at 13:50

This case it seems that these two algorithms is O(n) even though they are not similar. Count is being used differently, it looks like the first one uses count perhaps to show the size of the array that it changed. So if someone put an element in the array, count increments. But the second uses count for something else. Also the same for arr[i] = x;. First one seems to set it once, while the second one continues to set it.

A typical case of nested loop is like the following:


like if count = 100

   for(int j=100-1;j>=0;j--) // 100 times it must iterate 

  //then i turns to 1

  for(int j=100-1;j>=1;j--) //must iterate 99 times


If it was just one loop it will iterate only 100

 for(i=0;i<count;i++) //iterate 100 times that is it, its done

but with a nested loop it iterates

when i=0 : it iterates 100 times
when i=1 : it iterates 99 times
when i=2 : it iterates 98 times 

So in other words, if there was just one loop here it will only iterate 100 times But with this nested loop it is looping 100 times + 99 times + 98 times etc. This is most likely especially 'if(arr[i]>x) break;' never happens

Also according to Big Oh notation, if something takes (n(n-1))/2 times to complete, which this does, it is considered O(n^2)

  • But what about the break statement? Assume at i = 3, we have found our target. So far we have iterated 3 times, the J loop will iterate 97 times, then break! We have only iterated 100 times which would be equal to N. – Lifter Oct 10 '14 at 13:43
  • @Lifter for(i=0;i<count;i++) if(arr[i]>x) break; What if arr[i] is never greater than x. So iterated through the whole thing n^2 times instead. Using Big O notation means what is this code's worst case scenario. – Rika Oct 10 '14 at 13:53
  • @Rika If arr[i] is never greater than x, the inner loop will never be started, so the time would be O(N). I edited the original post to improve the formatting, and also the OP added a missing {, so that may make it easier to see what's going on. That may make it clearer that the code is actually O(N), since there is no case in which the inner for is started more than once, except possibly for cases in which it terminates immediately. – ajb Oct 10 '14 at 17:31
  • @ajb For the first code he wrote the inner loop will be started for there is no brackets so it will loop the first loop then the second one. So in that case if count = 100, it will loop 100 times, then loop 100 times again. – Rika Oct 10 '14 at 18:05
  • 1
    @Rika I don't understand--the first algorithm doesn't have any nested loops, so how can it be O(N^2)? – ajb Oct 10 '14 at 18:19

Your Answer

