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!

]]>