65 views

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

| 65 views
0
Hey.

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)
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)
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)