The Gateway to Computer Science Excellence
0 votes
65 views

$if ...F(n)=O(g(n)) Then ...it is true or false 2^{f(n)}=O(2^{g(n)}) Answer with reason$

in Algorithms by (5 points) | 65 views
0
Hey.

Please edit it more properly.

3 Answers

0 votes
Its not at all true.

For example: Take an algorithm which takes $2n$ steps and an another algorithm $B$ which takes $n$ steps. Then their ratio is constant.

But the ratio of $2^{2n}$ and $2^n$ is not at all constant.

So, it is definitely not true.
by Boss (13.2k points)
0 votes
It is not true because

let,f(n)=5n+1 then g(n) will be equalto 'n' i.e.,5n+1=O(n)

but, 2^(5n+1) isnot equal toO(2^n)
by (299 points)
0 votes
If $f(n)=O(g(n)),$ Then It means that

$f(n)\leq C_{0}. g(n)$;  Where $C_{0}$ is constant, $C_{0} > 0,$$n \geqslant n_{0} ,$ and $n_{0}\geq 1$

$2^{f(n)}\leq 2^{(C_{0}.g(n))}$ ;Raising power to both side  ----------- 1

 

 

If $2^{f(n)}=O(2^{g(n)}),$ Then it means that

$2^{f(n)}\leq C_1.2^{g(n)}$ ;Where $C_{1}$ is constant, $C_{1} > 0,$$n \geqslant n_{0} ,$ and $n_{0}\geq 1$

$2^{f(n)}\leq C_1.2^{g(n)}$ -------------2
 

Since 1 & 2 are not the same, Then we can say that it's not true.
by (57 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,492 answers
195,439 comments
100,695 users