If f (n) = Θ (g (n)) then 2 ^ f (n) = Θ (2 ^ g (n))?

Question

If f (n) is Θ (g (n)), then the function 2 ^{f (n) is} always Θ (2 ^{g (n)} )? Why or why not?

+2

2hype May 12 '10 at 15:20

1 answer

templatetypedef · Answer 1 · 2013-11-05T01:21:41+0000

This statement is false. Take f (n) = 2n and g (n) = n. Then f (n) = & Theta; (g (n)) because 2n = & Theta; (n).

However, 2 ^{f (n)} = 2 ²ⁿ = 4 ⁿ and 2 ^{g (n)} = 2 ⁿ but 4 ⁿ & ne; & Theta; (2 ^p ). You can see this because

lim _{n → & infin;}4 ⁿ / 2 ⁿ

= lim _{n → & infin;}2 ⁿ

= & infin;

Hope this helps!