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 &lt;- 0 to limit - 1 do
2.      min_index &lt;- j
3.      for k &lt;- j + 1 to limit do 
4.          if A(k) &lt; A(min_index)
5.              min_index &lt;- k
6.          end-if
7.      end-for
8.      temp &lt;- A(min_index)
9.      A(min_index) &lt;- A(j)
10.     A(j) &lt;- 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 &lt; \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}$.