CODEWITHSUNDEEP
java
Lifter
Lifter

Reputation: 77

Big O Notation for sorted insertion

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];
    arr[i]=x;
    count++;}

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;
        for (i=0; i<count; i++) { 
            if (arr[i]>x) {
                for (int j=count-1; j>=i; j--) {
                    arr[j+1] = arr[j];
                    arr[i] = x;
                    count++;
                    flag = true;
                }
                if (flag) 
                    break;
            }
        }
    }

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.

Upvotes: 0

Views: 113

Answers (1)

Rika
Rika

Reputation: 796

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:

  for(int j=count-1;j>=i;j--)

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

   etc...

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)

Upvotes: 2

Related Questions