CODEWITHSUNDEEP
big-otime-complexityquicksort
Mysty
Mysty

Reputation: 83

Why does this quote about quicksort's worst-case runtime use Ω notation?

I just read this excerpt from Introduction to Algorithms:

Quick sort takes Ω(n2) time when partition is unbalanced

How do I interpret this Ω(n2)? Why is it Ω? Could we have also used big-O notation here?

Upvotes: 1

Views: 443

Answers (2)

amit
amit

Reputation: 178491

It is actually even Theta(n^2) so it is also Omega(n^2), but the claim "Quick sort is O(n^2) when partition is unbalanced" is not very informative - since O(nlogn) is a subset of O(n^2). In other words, everything that is O(nlogn) (like quicksort average case), is also O(n^2).

big O gives upper bound, but here, we want to show lower bound - that in the worst case, we cannot go better than n^2, and not that we cannot go worse than it, and thus we are not using O(n^2). So, even the best case of quick sort is O(n^2) (but NOT Omega(n^2)) - thus saying quicksort is O(n^2) is not very informative.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 373012

Big-O notation, which is what you're probably used to, is used to describe upper bounds. If we say that an algorithm has runtime O(n2), we mean that runtime of the algorithm is at most some quadratic function. You can think of O notation as a "less than or equal to" sign.

Big-Ω notation is like big-O notation, but is used to describe lower bounds. If we say that an algorithm has runtime Ω(n2), we mean that the runtime of the algorithm is at least some quadratic functino. You can think of Ω notation as a "greater than or equal to" sign.

When we're talking about the worst-case runtime of an algorithm, big-O notation usually isn't appropriate. Let's say that I claim that the worst-case runtime of an algorithm is O(n2). What I'm saying is that the runtime of that algorithm is at most some quadratic function. That said, the worst-case runtime might be a lot lower than that. As an analogy, let's say that I claim that I'm at most 10,000 years old. This doesn't really say much - I'm definitely at most 10,000 years old, but I'm actually much younger than that.

On the other hand, let's say that I claim that the worst-case runtime of an algorithm is Ω(n2). Now I'm saying that the worst-case runtime of the algorithm is at least some quadratic function. That actually says something - going back to our previous analogy, if I tell you that some rock is at least one billion years old, that actually tells you something - it's pretty old! It's similar to the worst-case runtime being Ω(n2) - I'm telling you that it's at least quadratic, ruling out anything smaller.

Hope this helps!

Upvotes: 3

Related Questions