1

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?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Mysty
  • 83
  • 1
  • 7
  • It is O(n^2) in that case, but so is merge sort. Merge sort is not, however, Omega(n^2). – David Eisenstat Feb 18 '15 at 17:25
  • 1
    possible duplicate of [What is the difference between Θ(n) and O(n)?](http://stackoverflow.com/questions/471199/what-is-the-difference-between-%ce%98n-and-on) – anatolyg Feb 18 '15 at 17:32
  • @anatolyg I'm not sure this is an exact duplicate, since that linked question talks about Theta notation rather than Omega notation. – templatetypedef Feb 18 '15 at 17:32
  • 1
    @templatetypedef This question is not an exact duplicate. The linked question explains all relevant notation (including Theta and Omega). – anatolyg Feb 18 '15 at 17:34

2 Answers2

3

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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • I read the book again before i could read your answer and your answer is totally in accord with what i understood. I really appreciate the help! There's another excerpt from the book "Thus, the O(n^2) bound on worst-case running time of insertion sort also applies to its running time on every input." "For example, the best-case running time of insertion sort is Omega(n) which implies that the running time of insertion sort is Omega(n)." – Mysty Feb 21 '15 at 07:10
  • Reading this, i can say that running time of insertion sort algorithm is O(n^2) and also Omega(n). But i can not say that the running time for the algorithm is Theta(n^2)n or Theta(n) because when it comes to theta it has to be specific for Worst case inputs and best case inputs(in case the algorithm behaves differently for different inputs like in our case). I can make that statement " running time for the algorithm" only when algorithm behaves same for all inputs like merge sort. Please correct if i am wrong. – Mysty Feb 21 '15 at 07:11
0

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.

amit
  • 175,853
  • 27
  • 231
  • 333