Problem:
Let f and g be two increasing functions, defined on the natural numbers, with $ f(1) $ , $ g(1) \ge 1 $. Assume that $ f(n)=O(g(n)) $ . Is $ 2^{f(n)}=O(2^{g(n)}) $? (Multiple answers may be correct, check all that apply.)
Solution:
This is simply an assignment problem I have done before, it can be found in the link below.
Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 3
The key idea is just going back to the definition and argue the necessary condition for $ 2^{f(n)}=O(2^{g(n)}) $ is $ f(n) \le g(n) $.
Let f and g be two increasing functions, defined on the natural numbers, with $ f(1) $ , $ g(1) \ge 1 $. Assume that $ f(n)=O(g(n)) $ . Is $ 2^{f(n)}=O(2^{g(n)}) $? (Multiple answers may be correct, check all that apply.)
Solution:
This is simply an assignment problem I have done before, it can be found in the link below.
Algorithms: Design and Analysis, Part 1 - Problem Set 1 - Question 3
The key idea is just going back to the definition and argue the necessary condition for $ 2^{f(n)}=O(2^{g(n)}) $ is $ f(n) \le g(n) $.
No comments:
Post a Comment