# Running time of selection sort

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

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

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