[bmcfeeley]

Big-Theta is not an average case, it is a special form of Big-O and Big-Omega wherein the worst case is also the best case from a complexity perspective.

This is sometimes true in sorting since comparison based sorting cannot be improved beyond n*log(n) except in specific cases for specific domains.

You are absolutely on the money about worst case being O(n^2) though for quicksort.

[maxk42]

I stand corrected. Is there a notation for "average" complexity?

[bmcfeeley]

Not that I'm aware of! As you've seen, I see Big-O abused into shorthand for "on the order of" to the effect of "average case is O(nlog(n))"