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.