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?