CODEWITHSUNDEEP
javatime-complexityspace-complexity
MasterYoshi
MasterYoshi

Reputation: 57

Finding big O recursion

I'm trying to figure out what is Big O and big Omega from the following piece of code down below.

This code inputs an array of ints, and sorts them in ascending order. The worst case would be all in descending order {5,4,3,2,1} ,and the best case would be ascending order {1,2,3,4,5}.

static int counter = 0;
static int counter1 = 0;
static int counter2 = 0;

public static int[] MyAlgorithm(int[]a) {
    int n = a.length;
    boolean done = true;
    int j = 0;
    while(j<=n-2) {
        counter++;
        if(a[j]>a[j+1]) {
            int temp = a[j];
            a[j] = a[j+1];
            a[j+1] = temp;
            done = false;
        }
        j = j+1;
    }
    j = n-1;
    while(j>=1) {
        counter1++;
        if(a[j]<a[j-1]) {
            int temp = a[j-1];
            a[j-1] = a[j];
            a[j] = temp;
            done = false;
        }
        j = j-1;
    }
    if(!done) {
        counter2++;
        MyAlgorithm(a);
    }
    return a;

}

Worst case for each while loop i got was n-1, and for the recursion it was n/2.

Best case is n-1 while loops, and zero recursion

So my big Omega is (n) ( no recursion ) but for Big O, here is the confusing part for me, since there are n/2 recursion calls, does this mean i do N X N (because of n/2 recursion) big O (n^2)? or does it stay big O(n)???

Upvotes: 0

Views: 118

Answers (1)

gue
gue

Reputation: 2018

As you said the Omega is Omega(n). In case all numbers in the array a are already in sorted order the code iterates over the array twice, once per while loop. This are n steps O(1) times.

In the worst case you are correct in assuming O(n^2). As you saw, an array sorted in reverse order produces such a worst case scenario. We can also produce a worst case scenario by having a sorted array in increasing order and then only swap the first and last number. Then each run of MyAlgorithm moves that last/first number two positions. After n/2 steps (runs of MyAlgorithm) the numbers reach their final position. Hence, O(n/2 * n) = O(n^2).

Small side note, sorting in general is in O(n log n), so you can sort something only under some circumstances in O(n).

Upvotes: 1

Related Questions