What exactly does it mean when an algorithm has a run time of Omega(nlgn) or Theta(n^2), etc. From what I can tell, Big O is used to show the worst case(?) while Omega is best(?) and Theta is either(in between O and Omega?. I'm having a hard time understanding this topic. The reason I ask is because the book would ask questions like :

"Show that the running time of QUICKSORT is Theta(n^2) when the array A contains distinct elements and is sorted in decreasing order."


"What is the running time of QUICKSORT when all eleents of array A have the same value?"

How do you solve problems like these?

Edited by SeePlusPlus2

5 Years
Discussion Span
Last Post by sepp2k

The distinction between O, Theta and Omega isn't about best- versus worst-case. You can use any of these notations to analyze any case you want. That is, the statements "QuickSort's worst case is in Theta(n^2)" and "QuickSort's best case is in Theta(n log n)" are both valid usages of Theta.

Instead the distinction is that O specifies an upper bound, Omega a lower bound and Theta both. What this means is that "Foo is in O(n^2)" means that Foo is quadratic or less (that is when something is linear, it's also in O(n^2) because linear is less than quadratic). Similarly Omega(n^2) means quadratic or more (that is something qubic or even exponential will also be in Omega(n^2)). Theta(n^2) means it's exactly quadratic. That is when something is quadratic, it's in Theta(n^2), but something that's linear, cubic or exponential is not. Something is in Theta(f(n)) if it is both in O(f(n)) and Omega(f(n)).


How can you tell what an algorithm's run time notation is by looking at it?

Edited by SeePlusPlus2


Do you mean "how to tell what an algorithm's run time is" or "how to tell which notation to use (i.e. O or Theta or Omega)"? If you mean the latter: You should use the notation that the assignment asks for. when in doubt, use Theta as its the most specific.

If you mean the former: The basic approach is to understand exactly what the algorithm does and then ask yourself how many steps it will take for a given n. Of course that's easier said than done. Plenty of tutorials have been written about this.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.