[geofft]

The subtlety here is basically that big-O and big-omega and friends are ways of characterizing functions, and functions map one input to one output. "Running time of a problem of size n" is not a function; it has a range of possible values for a given n. "Maximum running time of a problem of size n" is a function. That function itself, an² + bn + c for some constants a, b, and c, has lower and upper asymptotic bounds.

I thought you were right at first but then realized what was going on. This is a pretty subtle point and mostly uninteresting for well-understood algorithms like quicksort. But one slightly less subtle point is that big-theta isn't average case, it is the combination of big-O and big-omega, i.e., bounded from above and below (possibly with different constant factors) by the same asymptotic behavior.