# Selection Sort Analysis

I'm having difficulty understanding the big-O analysis of the selection sort algorithm. Here is my pseudocode (with line numbers):

    procedure SELECTION (A(n), limit)
1.  for j <- 0 to limit - 1 do
2.      min_index <- j
3.      for k <- j + 1 to limit do
4.          if A(k) < A(min_index)
5.              min_index <- k
6.          end-if
7.      end-for
8.      temp <- A(min_index)
9.      A(min_index) <- A(j)
10.     A(j) <- temp
end-for
end-SELECTION


Our professor wants us to work from the inside out; in other words, analyze the statements the furthest away from the conceptual vertical line that denotes hierarchies. Therefore, I start at line 5, and work out from there. Here's what I've understood so far:

• The time complexity of lines 4-6 is O(1) (constant).
• Because lines 4-6 are "contained" in the for loop on line 3, you must use the rule of sums to multiply line 3 and lines 4-6. In other words, if line 3 is a program fragment f(x) and lines 4-6 are a program fragment g(x), then the time complexity of lines 3 - 6 is f(x) * g(x).

This is where I get confused. Because var limit is referencing the size of the array, wouldn't the for loop on line 3 run limit-1 times, because k is equal to 1 and is running to limit? To put it another way, if k were equal to zero, wouldn't the loop run limit times? Every video and website I've looked at has not given me a clear representation of that expression, because they've analyzed it differently.

On top of this question, how do I determine which asymptotic notation to use to describe this problem? Is it Big-Oh, Big-Omega or Big-Theta?

Thank you.

The number of iterations of the loop 3–7 depends on the value of $$j$$: it is $$\mathit{limit} - j$$. Therefore the running time of lines 3–7 is $$O(\mathit{limit} - j)$$. Lines 8–10 run in $$O(1)$$ time, so the body of the loop 1–11 runs in time $$O(\mathit{limit}-j) + O(1) = O(\mathit{limit}-j)$$ (using $$j < \mathit{limit}$$). Finally, the total running time is $$O\left(\sum_{j=0}^{\mathit{limit}-1} \mathit{limit}-j\right) = O\left(\sum_{j=1}^{\mathit{limit}} j\right) = O(\mathit{limit}^2),$$ using the formula $$\sum_{j=1}^n j = \frac{n(n+1)}{2}$$.