CODEWITHSUNDEEP
algorithmsortingbig-otime-complexityselection-sort
Hatik
Hatik

Reputation: 1159

Calculating the big-O complexity of this selection sort implementation?

I'm trying to compute the big-O time complexity of this selection sort implementation:

void selectionsort(int a[], int n)                    
{
    int i, j, minimum, index;                       
    for(i=0; i<(n-1); i++)                       
    {
        minimum=a[n-1];                      
        index=(n-1);                             
        for(j=i; j<(n-1); j++)                   
        {
            if(a[j]<minimum)                     
            {
                minimum=a[j];                               
                index=j;
            }
        }
        if (i != index)
        {
            a[index]=a[i];
            a[i]=minimum;
        }
    }
}

How might I go about doing this?

Upvotes: 1

Views: 7307

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

Formally, you can obtain the exact number of iterations with the order of growth using the methodology below:

enter image description here

Executing the following fragment code (synthetic version of the original code), sum will equal the closed form of T(n).

sum = 0;
for( i = 0 ;  i < ( n - 1 ) ; i ++ ) {    
    for( j = i ; j < ( n - 1 ) ; j ++ ) {
        sum ++;
    }
}

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 373012

Let's begin by looking at the inside of the outer loop. It does O(1) work with the initial assignments, then has a loop that runs n - i times, then does O(1) more work at the end to perform the swap. Therefore, the runtime is Θ(n - i).

If we sum up from i going from 0 up to n - 1, we get the following:

n + (n - 1) + (n - 2) + ... + 1

This famous sum works out to Θ(n2), so the runtime would be Θ(n2), matching the known runtime of this algorithm.

Hope this helps!

Upvotes: 1

Related Questions