Math Is Fun Forum

Nicomachus

Member

Registered: 2012-08-26

Posts: 1

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!

anonimnystefy

Real Member

From: Harlan's World

Registered: 2011-05-23

Posts: 16,049

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).

---

“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.