- the Ɵ() and O() notations can be used on mathematical function. For example 5n^2 + 3n = Ɵ(n^2) [^1] or 3n^2 = O(n^3).
- algorithms have different complexities: for best case, for worst case, or average case. It corresponds to as many mathematical functions.
Each of these functions can be given appropriate Ɵ() or O() bounds.
[^1]: really meaning λn.5n^2 + 3n ∈ Ɵ(λn.n^2), it's a relation between functions.
And if a stackoverflow link isn't good enough, than go read CLRS, Dasgupta, or Skiena.
Quicksort has no Theta(x), it is O(n^2) and Omega(n log n) with an expected runtime of n log n. The reason that Quicksort performs so well is because it is only in very specialized cases where it devolves to its worst case.
[1] http://stackoverflow.com/questions/10376740/big-theta-notati...
Edit: Replied to the wrong commenter, so the replied to post isn't wrong, the grandparent post is.
1. Theta(n) means that it's O(n), O(n^2), O(...), but
Theta(n) is a proper, tighter definition of the upper
bound. It doesn't say anything about the lower bound.
2. Theta(n) means that it's tightly bounded up and down
by n. Both Omega(n) and some O(n) are equal, thus its
Theta(n).