Hacker News new | ask | show | jobs
by anseladdams 3695 days ago
> For example Quicksort is O(n^2) but Omega(nlogn) it is neither Theta(nlogn) nor Theta(n^2).

No, this is flat out wrong. Big O is an upper bound on an asymptotic growth rate. Big Omega is a lower bound on the asymptotic growth rate. Big Theta is a tight bound on the asymptotic growth rate. These are independent to the average case, best case, or worst case run time of a given algorithm.

Quicksort has an average run time of Theta(n lg n). Equivalently, its average run time is O(n lg n) and Omega(n lg n). It has a worst case run time of Theta(n^2). Equivalently, its worst case run time is O(n^2) and Omega(n^2).

> Actually we don't use it informally as big-Theta,

Wrong again.
2 comments
SamReidHughes 3695 days ago
You can state that quicksort has run time O(n^2). The function you're describing with O(n^2) is f : S -> R, where S is the set of input values and R is the set of real numbers, and f(x) is the running time of running quicksort on input value x, and n : S -> N is the size of input value x. The notation O(g(n)) describes the function f in terms of the function n.

That f is in O(g(n)) means there exist constants C and N_0 such that for all x in S, provided that n(x) >= N_0, it is true that |f(x)| <= |C g(n(x))|.

And that f is in Omega(g(n)) means there exist C > 0 and N_0 such that for all x in S, provided that n(x) >= N_0, it is true that |f(x)| >= |C g(n(x))|.

link
Scea91 3695 days ago
Perhaps it is you that need to be educated.

They are independent only if you explicitly state that you are computing them for best/average/worst case independently. Is it commonly done? Sure. But there is nothing in the definition that forces us to do that.

If the things were as you state would you have any use for Omega and Omicron then? Wouldn't just Theta suffice?

link
anseladdams 3695 days ago
> But there is nothing in the definition that forces us to do that.

That's true. You're right.

> If the things were as you state would you have any use for Omega and Omicron then? Wouldn't just Theta suffice?

Couldn't there be cases where we don't have a known tight asymptotic bound but do have an upper and/or lower bound? And although it's an abuse of notation, you do often see big-O used in place of Theta. From CLRS:

"In the literature, we sometimes find O-notation informally describing asymptotically tight bounds, that is, what we have defined using Theta-notation."

link