Omega And Theta

[scottwhudson]

In some of these tables (e.g. array sorting), a 'best' and 'average' case are included along with the worst case, and they use the big O notation as well. Are the best case runtimes of these algorithms not Omega and Theta, respectively?

I'm in the process of beefing up my CS theory and there seems to be a ton of conflicting information in the community about asymptotic analysis and Big O notation. Not trying to nitpick on this (and my understanding of this could be off-base), but wouldn't the best case runtime for an algorithm be represented as Ω(n) and the average as ϴ(n), not O(n) since Big O implies the worst case?

[ericdrowell]

Thanks for the note. I double checked, and the definitions of O, omega, and theta are:

f(x) = O(g(x)) (big-oh) means that the growth rate of f(x) is asymptotically less than or equal to to the growth rate of g(x).

f(x) = Ω(g(x)) (big-omega) means that the growth rate of f(x) is asymptotically greater than or equal to the growth rate of g(x)

f(x) = Θ(g(x)) (theta) means that the growth rate of f(x) is asymptotically equal to the growth rate of g(x)

Although Omega and Theta don't mean best and average, I think you might be right that it would be more clear to use Omega for the lower bound, and Theta for the average bound. However using big O is still also technically correct. I'll think on it some more.

[ericdrowell]

@scottwhudson I decided to go ahead and use omega for best case, and theta for average case. Thanks!

[bisgardo]

Sorry, but I disagree.

First of all, this way of writing might cause readers to wrongly get the impression that Ω means best case, Θ means average, and big O means worst. I know that this is not what the author believes, but the table indicates it.

Secondly, since you write that big O is also technically correct, you might as well write Θ since this is a stronger statement. In fact, the current notation opens up the possibility that the "best" case may be worse than "worst" by an arbitrarily large amount.

Lastly, it is my understanding that omega is mostly useful for providing lower bounds on algorithmic problems rather than concrete algorithms. That is, for proving that no algorithm with a better big O time than the lower bound can exist.

I might be wrong on the last item, but think the first two should be sufficient argument to use the most precise notation available.