I believe Big Theta means bounded above and below by `n^2`, where the bounds differ by a constant factor. Saying that Quicksort is Ɵ(n^2) means that is has worst case `n^2` AND best case `n^2`. But the best case of Quicksort is `n`.
So Quicksort is O(n^2); the worst case is <= cn^2, for a constant c.
Sorry to bring it up. I was wondering if I wanted to be the annoying guy who nitpicks on that; but then I thought you might be interested in the difference.
[edit1: was wrong, don't want to mislead]
[edit2: not sure I was wrong anymore, this is confusing]
So Quicksort is O(n^2); the worst case is <= cn^2, for a constant c.
Sorry to bring it up. I was wondering if I wanted to be the annoying guy who nitpicks on that; but then I thought you might be interested in the difference.