I mean you say "best case O(n)" if the best case is Theta(n), even though the algorithm may be quadratic on average. You don't say the best case is O(n^2) if t

I mean you say "best case O(n)" if the best case is Theta(n), even though the algorithm may be quadratic on average. You don't say the best case is O(n^2) if the best case is Theta(n log n) even though technically that would be correct.