[matyasrichter]

Big Theta isn't "average case". It describes an algorithm with the same asymptotic lower and upper bounds. How would you even formally define an average case, when the result depends on the input?