[Solved]: Running time of selection sort

Problem Detail: 

I wrote pseudocode for Selection Sort, but I'm not sure what is the running time of my algorithm, can you help me with that?

---

My Pseudocode: Selection Sort(int a[], int n)

Input: array of length $n$

Output: sorted array

for r=1 to n     min=a[r]     for i=r to n         if (a[i]<min)               min=a[i]               k=i               a[k]=a[r]               a[r]=min 

The external for takes $\Theta (n)$ but I'm not sure about the internal for because it depends on $r$.

Asked By : Nehorai

Answered By : Yuval Filmus

If the body of the outer loop gets executed $A$ times and the body of the inner loop gets executed $B$ times, then your algorithm runs in time $\Theta(A+B)$. After calculating $A$ and $B$, you will discover that $B$ grows faster than $A$, and so the running time of your algorithm is dominated by the number of times the body of the inner loop gets executed. It remains to calculate (or estimate) $A$ and $B$. You already mentioned that $A = n$. So all you need to complete the exercise is to calculate $B$, a task which I leave to you.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54562

 Ask a Question

 Download Related Notes/Documents