Go Class data structure asymptotic notation practice video question 21

Answer 1

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.

Comments

@prajjwal_191 thanks for the answer . my fault was that I thought they took c=1 while solving this question so I thought how can 2n becomes less than n in any instance. But after your answer I got what they really meant. Again thanks for your time.