434 views

1 Answer

Best answer
1 votes
1 votes
BIG-Oh means :

if there are two functions f(n) and g(n) such that

f(n) <= C.g(n) where exists two constants C and n0 such that C>0 and n>=$n_{0}$

then f(n)= O(g(n))

that means if using a constant C we can prove f(n)<=C.g(n) for any value of n>= $n_{0}$ then we can say f(n)=O(g(n)).

 

so for your question if f(n)=2n and g(n)=n then if we can prove f(n)<=C.g(n) for all n where n>= constant $n_{0}$, then we can say 2n=O(n).

to prove that let constant C=3 then

f(n)<=3 g(n) from all n greater or equal to $n_{0}$ = 1 onwards

2n <= 3n    from all n greater or equal to $n_{0}$ = 1 onwards. hence it is proved that 2n=O(n).

 

now, $2^{f(n)}$ = $2^{2n}$  and  $2^{g(n)}$ = $2^{n}$

here we can see f(n)> g(n) by $2^{n}$ times hence using any constant we can't prove that $2^{f(n)}$ = O($2^{g(n)}$)

so if,   f(n)= O(g(n)) then  $2^{f(n)}$ = O($2^{g(n)}$)  need not be true always.

i hope your doubt is cleared now, Thankyou.
selected by

No related questions found