Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: √ ∞ ≠ ≤ ≥ ≈ ⇒ ∈ Δ θ ∴ ∑ ∫ π -

Login

Username

Password

Not registered yet?

#1 2012-08-27 07:51:23

Nicomachus
Novice

Offline

Big Theta Notation

In the book that I am studying, Big Theta Notation isn't explained very well and there examples are quite terrible. After looking online for explanations of Big Theta Notation I think that I have gotten at least a basic grasp on it, but there are still some questions I can't answer.

True/False:

1. Theta Notation is an effective measure of algorithm efficiency when the expected input size for the algorithm is small.
      -The book says that Theta Notation is used to describe situations where we have a tight upper (and lower) bound. So based on that it, it makes me want to say that this problem is true. But if you consider a function            like f(n) = n+1000n , wouldn't that mean that f(n) = θ(n) ? If so, that would be a very ineffective measure of algorithm efficiency when the expected input size is small.

2. All O(n) algorithms are θ(n).
     -I'm thinking this one is false because to be θ(n) a function would have to be both O(n) and Omega(n).

3. All  θ(n) are O(n).
     - I'm pretty sure this one is true based on the same logic as 2.

Also, as an application of that same logic, if you were given code fragments and asked to give a theta analysis of them, could you simply calculate the Big O value of that code and say that the Big Theta would have to be the same (assuming it existed).

And finally, if anyone could give an example of a function that would have a Big O value that is different from it's Big Omega value it would be very helpful. I'm having a hard time understanding how a function can exist that would not have equivalent Big O and Big Omega values.

Thanks in advance for any help!

#2 2012-08-27 11:26:40

anonimnystefy
Real Member

Offline

Re: Big Theta Notation

I think all of your answers to the true or false questions are preety much correct. The question you asked about a case where big oh differs from big theta is simply answered. Consider the function f(n)=n^2. It is certainly both O(n^3) and BigTheta(n^2).


The limit operator is just an excuse for doing something you know you can't.
It's the subject that nobody knows anything about that we can all talk about! ― Richard Feynman
Taking a new step, uttering a new word, is what people fear most. ― Fyodor Dostoyevsky, Crime and Punishment

Board footer

Powered by FluxBB