4 ms·

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

by emillon 12y ago

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.

dlp211 12y ago
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-notation-what-exactly-does-big-theta-represent 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.
- emillon 12y ago
  I was confused at first :)
- AYBABTME 12y ago
  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.

by emillon 12y ago

dlp211 12y ago

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-notation-what-exactly-does-big-theta-represent 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.

emillon 12y ago
I was confused at first :)
AYBABTME 12y ago
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.