The difference between big theta and big O has nothing to do with worst vs. average case. They are two completely orthogonal axes. You can talk about the big-O

The difference between big theta and big O has nothing to do with worst vs. average case. They are two completely orthogonal axes. You can talk about the big-O of the average case, the big-theta of the average case, the big-O of the worst case, or the big-theta of the worst case.