big-Oh

[HypnotiC]

Hi every one ...

plz can any one help with finding the big-Oh characterizations in terms of n, of the running time for the following method


void SelectionSort( int[] A ) {

int Minposition, temp, I, J;

for( I = n-1; I > 0; --I ) {
Minposition = I;

for( J = 0; J < I; ++J ) {
if( A[J] < A[ Minposition ] )
Minposition = J;
}

temp = A[I];
A[I] = A[ Minposition ];
A[ Minposition ] = temp;
}
}

[cma]

Here's one way to look at it, your first loop traverses the entire array, A, so that is O(n), the inner loop is a little more interesting, depending on what position I is on, it can loop, none, it can loop through all the elements of A or somewhere in between, with this, you can take the average of the two extreme cases, it can either loop 0 times or it can loop n-times (n=all the elements of A), (0 + n)/2 = n/2. Now, in this case, because the loops are nested, you multiply: n * (n/2) = (n^2)/2, you drop the constant and you're left with your running time: O(n^2).

Note, the reason why you multiply them, in case you didn't know is because the loops are nested, look at this piece of C++ code and see if you can find out what the value of count will be:

int count = 0
for (int i = 0; i < 10; i++)
{ for (int j = 0; j < 5; j++)
{ count++; }
}
cout << count;

and look at this to see what count will be in this version:

int count = 0
for (int i = 0; i < 10; i++)
{ count++ }
for (int j = 0; j < 5; j++)
{ count++; }
cout << count;


Other's may have a different way to come up with the running time of selection sort, and may disagree with what I posted, but they will all have the same conclusion, quadratic running time.