2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Actually, the external for doesn't take $\Theta(n)$, since it contains the internal for. $\endgroup$ – Yuval Filmus Mar 16 '16 at 20:36
  • $\begingroup$ @YuvalFilmus It is for within for $\endgroup$ – 3SAT Mar 16 '16 at 20:45
  • $\begingroup$ The external for has $\Theta(n)$ runtime on its own, plus the runtime from the internal for. $\endgroup$ – DylanSp Mar 16 '16 at 20:48
1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

The inner loop will iterate $n - r + 1$ times for each iteration of the outer loop. To find the total runtime, we can sum this expression over $r = 1$ to $r = n$: \begin{align*} \sum_{r = 1}^{n} (n - r + 1) &= n^2 - \left(\sum_{r = 1}^{n} r\right) + n \\ &= n^2 - \frac{n(n + 1)}{2} + n \\ &= \frac{1}{2}n^2 + \frac{1}{2}n \end{align*} which is $\Theta(n^2)$.

To simplify the proof, we can note that the sequence $(n - r + 1)_{r \in [1, n]}$ is just the sequence $1, 2, \ldots, n$, which you can see by substituting $r = 1$ and $r = n$ into $(n - r + 1)$. We know that this sum $\sum_{i = 1}^{n} i$ equals $\frac{n(n + 1)}{2}$, giving the same result as the first method.

$\endgroup$
  • $\begingroup$ If I could, I would up vote you 5 times, thank you for good answer $\endgroup$ – 3SAT Mar 16 '16 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.