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
