[triplenineteen]

Hmm. Big O already encompasses "at worst".

Theta is the notation for a single case, be it the worst case, the best case, one run of a randomized algo, etc.

At least that is my understanding.

[ephemeralgomi]

Big O is an upper bound, little o is a lower bound. Big theta means both an upper and lower bound.