# The Algorithm Design Manual - Working with the Big Oh

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

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)$$

• Thanks, really helped a lot :). – kasra Jan 18 at 19:30