Sort Alrgorithm time complexity

Question

void MySort(table T[0..n-1]: array of integers) 
{
   for m = 0 to n-2 do //will run n+1
   {
     j = m; // will run n times
     for k = m+1 to n-1 do /will run n^2 +n
     {
        if T[k] < T[j] then j = k; //will run n^2 times
     }
     swap(T[m], T[j]); //will run 3*n times
   }
} 

I have to find the time complexity of this algorithm, and find the category it belongs. So i calculate it will run 2n^2+6n+1 and it's category is O(n^2) I would like to know if i am correct, and another question is is Ω also n^2 and Θ also n^2 ?

Answer 1

According to the definitions on wikipedia (http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations)

Big Omicron O - function is bounded above (by up to constant factor) asymptotically
Your analysis of O(n^2) is correct (though your anyalysis of swap is wrong)

Big Omega Ω - function is bounded below asymptotically
Your analysis of Ω(n^2) is correct (though your anyalysis of swap is wrong)

Big Theta Θ - is bounded both above and below by g asymptotically
As the Big Omnicron and Big Omega are the same, the big Theta is the same as those two: Θ(n^2)

---

As for detailed analysis of each part:
The outside-loop does run n-1, and there's one inner-loop and swap per iteration of that. Ergo, there is n-1 swaps as well.

The inner-loop-body runs n-m times for each m, which is where the math gets complicated. The T[k] < T[j] gets executed ((n-1)-1)(n-2)/2 = (n^2)/2+2-2 times (I think).

The j = k is harder still, because now probability gets involved. I think it's the sum of lg(m) where m is the numbers 1 to n-1. After much math, I think that's lg(n!)/0.60206, and no, I have no idea where that constant came from or what it means.

---

You should know, your code is a Selection Sort, and the wikipedia page on selection sorts backs up my thoughts.

Answer 2

You can simply proceed like the following: