Comment by Dylan16807
2 years ago
> Yes what you're describing is theta - both an upper and lower bound (within constant factor).
No, I'm not.
A tight upper bound is only sometimes the same thing as theta.
Insertion in a vector or a hash table is best case 1, average case 1, worst case n. Quicksort is average case nlogn, worst case n^2. Bubble sort is best case n, average case n^2, worst case n^2.
None of those algorithms are bound above and below by the same function.
When Theta exists, it does imply that the upper bound is tight. Which is the feature that's actually important. But Theta talks even more about the lower bound, which rarely matters. Theta is not what you're actually looking for the vast majority of the time.
I still can't think of a single situation where I care about "lower bound within constant factor". I care about average time, I care about upper bounds, occasionally I want an algorithm where the time is always exactly the same for a particular n. But not asymptotic lower bound.
Preventing smartass answers for "upper bound" is a good goal, but the way you do that is not by switching to Theta.
For this purpose, when you say 'best case'/'average case'/'worst case', those are three different functions. Or normally/in general we'd talk about worst case.