2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you so much! Your answer is the most helpful I have been able to find so far. $\endgroup$ – Nat Porter Sep 23 '18 at 16:54

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.