Hacker News Reader

Comment by AYBABTME | Hacker News Reader

I believe Big Theta means bounded above and below by `n^2`, where the bounds differ by a constant factor. Saying that Quicksort is Ɵ(n^2) means that is has worst case `n^2` AND best case `n^2`. But the best case of Quicksort is `n`.

So Quicksort is O(n^2); the worst case is <= cn^2, for a constant c.

Sorry to bring it up. I was wondering if I wanted to be the annoying guy who nitpicks on that; but then I thought you might be interested in the difference.

   [edit1: was wrong, don't want to mislead]
   [edit2: not sure I was wrong anymore, this is confusing]

View on HN

No, it means the worst case is bounded above and below by n^2. That is, the worst-case scales no worse or better than n^2, but approximately proportional, asymptotically. (Whereas, for example, every O(n^2) algorithm also happens to be O(2^n))

The best case is something entirely separate, and can itself be bounded from above or below.

It doesn't make sense to say there's an upper and lower bound on the "worst" case. If that were true, the upper bound would be the new worst case, and the lower bound would be some middle case. A best or worst case is inherently always going to be big-theta.

This talks about our ability to reach or describe the worst case, so if we say it's Ɵ(n^2), we're saying that we can tell that the worst case is at least quadratic, and it's also no worse than quadratic. We might not be so good at the math and have only discovered that the worst case was at least linear and no worse than exponential (which is true of quicksort).

To help you wrt your edit 2, you seem to be confusing two things:

- the Ɵ() and O() notations can be used on mathematical function. For example 5n^2 + 3n = Ɵ(n^2) [^1] or 3n^2 = O(n^3).

- algorithms have different complexities: for best case, for worst case, or average case. It corresponds to as many mathematical functions.

Each of these functions can be given appropriate Ɵ() or O() bounds.

[^1]: really meaning λn.5n^2 + 3n ∈ Ɵ(λn.n^2), it's a relation between functions.

Except you are wrong. O(x) is an upper bound, Omega(x) is a lower bound, and something is Theta(x) iff it is bounded by Omega(x) and O(x) where (x) is the same[1].

And if a stackoverflow link isn't good enough, than go read CLRS, Dasgupta, or Skiena.

Quicksort has no Theta(x), it is O(n^2) and Omega(n log n) with an expected runtime of n log n. The reason that Quicksort performs so well is because it is only in very specialized cases where it devolves to its worst case.

[1] http://stackoverflow.com/questions/10376740/big-theta-notati...

Edit: Replied to the wrong commenter, so the replied to post isn't wrong, the grandparent post is.

I was confused at first :)

After reviewing, I've understood two meanings people give to Theta(n):

    1. Theta(n) means that it's O(n), O(n^2), O(...), but 
       Theta(n) is a proper, tighter definition of the upper
       bound.  It doesn't say anything about the lower bound.

    2. Theta(n) means that it's tightly bounded up and down 
       by n. Both Omega(n) and some O(n) are equal, thus its 
       Theta(n).

I think 2 is the proper definition (thus my 2nd edit), but I'm not totally sure. I've let my original comment there with the edit chain in hope discussions would bring up the proper definition. Unfortunately I'm getting downvoted for that, which I find odd.

Saying it is bounded by O(n²) is too vague, because it's the same as being bounded by O(n³) and so on. A linear algorithm is also O(n²) and O(n³).

That is why I emphasized that the worst case in particular has its bound within a constant factor of n², hence Ɵ.

Reply on news.ycombinator.com