Comment by 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.