Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 Help Me ! » Big Theta Notation » 2012-08-26 09:51:23

Nicomachus
Replies: 1

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!

Board footer

Powered by FluxBB