@ Gajedi: They might look alike but they are different. Big-O doesn't HAVE to be a worst case. How would you then explain the best case running time of an insertion sort to be O(n), average case to be O(n²) and worst case be O(n²)? A worst case running time could have a Theta(n) or a Omega(n) notation (sorry in the previous thread I wrote sigma for omega). It all depends. Normally for sorting we use big-O in ALL cases (be it worst, average or best). But for other things, for eg. the worst case running time of inserting or finding a key in a hash table is always Theta(n).

I have the following lecture from UCBerkeley that might make it clear for you. The link to this lecture is http://www.eecs.berkeley.edu/~jrs/61b/lec/21 . Scroll down the paragraph before the title "ALGORITHMIC ANALYSIS"

"Remember that the choice of O, Omega, or Theta is _independent_ of whether
we're talking about worst-case running time, best-case running time,
average-case running time, memory use, annual beer consumption as a function of
population, or some other function. The function has to be specified.
"Big-Oh" is NOT a synonym for "worst-case running time," and Omega is not a
synonym for "best-case running time."