Hello All, I need help making sure I am right about this. Say for example I have these two functions: f(n) = 2^n and g(n) = 3^n.
Now the order is O(2^n) and O(3^n) respectfuilly. Now I need make sure I am right about this: based on the order, O(2^n) < O(3^n) therefore f(n) < THETA(g(n)).
Is this statement correct here when I say f(n) < THETA(g(n)) and that O(2^n) < O(3^n)?
Tac-Tics
Sep22-08, 01:07 PM
Isn't O(2^n) = O(3^n)? Exponential functions differ by a multiplicative constant.
Jarle
Sep22-08, 01:15 PM
Isn't O(2^n) = O(3^n)? Exponential functions differ by a multiplicative constant.
No?
The constant C does not exist such that C \cdot 2^x > 3^x for all x.
Tac-Tics
Sep22-08, 02:28 PM
Ack. My intuition failed me. I was thinking of 2x^n versus 3x^n for a constant n. Sry.
CRGreathouse
Sep22-08, 02:41 PM
O(2^n) is O(3^n) in the usual abuse of notation sense. But the set of functions that are O(2^n) is a proper subset of the set of functions that are O(3^n). For example, 2.0001^n is not O(2^n).
"f(n) < THETA(g(n))" isn't defined -- O, o, Theta, and the others use only the element operator (or, by the abuse mentioned above, an equal sign). Do you perhaps mean that 2^n is o(3^n)? That would be correct, because lim 2^n/3^n = 0.
Ad2d
Sep22-08, 03:07 PM
Thank You all. I was able do what CRGreathouse with the limits which made more since to me. From what the professor was saying, I am thinking that Theta is a value that is im between the upper and lower bound, and I need to show whether or not the functions where less than the upperbond (f(n) < theta (g(n)) ), greater than the lower bound (f(n) > theta (g(n)) ), or equal ((f(n) = theta (g(n)) )). I hope that make sense (I'm not a genius when it comes to wording in math). Just like to say thanks again for all your input. It helped.