1
$\begingroup$

I'm reading The Algorithm Design Manuel and one part is kind of confusing to me

The part that's confusing to me is how in the "Proving the Theta" section he proves that selection sort is Ω(n^2). I mean, I understand that for some (c) c.n^2 can be a lower bound for selection sort, however I don't understand how he proves this in that section.

I would really appreciate it if you could help me understand that part. Thanks. .enter image description here

enter image description here

$\endgroup$
1
$\begingroup$

It is difficult to avoid what is repeating what is in the text, but you have exactly:

$T(n) = (n-1)+(n-2)+\ldots+1+0 =n\tfrac{n-1}{2} = \tfrac12n^2 -\tfrac12n$

and as an upper bound taking each value up to $n-1$:

$T(n) \le (n-1)+(n-1)+\ldots+(n-1)+(n-1) =n(n-1) = n^2-n$

and as an lower bound taking values of at least $\tfrac n2$ down to $\tfrac n2$ and other down to $0$ $($assuming $n$ is even; the odd case gives $\tfrac14n^2+\tfrac14 n)$:

$T(n) \ge \tfrac n2 +\ldots +\tfrac n2 +0+\ldots +0 = \tfrac n2 \times \tfrac n2 +\tfrac n2 \times 0 = \tfrac14n^2$

Since all three are essentially of the order of $n^2$ up to a constant, you can conclude $T(n)$ is $O(n^2)$ and $\Omega(n^2)$ and so $\Theta(n^2)$

$\endgroup$
1
  • $\begingroup$ Thanks, really helped a lot :). $\endgroup$ – kasra Jan 18 at 19:30

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.