If $f(n) = O(g(n)) \Rightarrow \log(f(n)) = O(\log(g(n))$ But not $2^{f(n)} = O(2^{g(n)})$, why?

33 Views Asked by At

I know that:

$$ f(n) = O(g(n)) $$

Namely:

$$ \exists c > 0, \exists N \in N, \forall n > N: f(n) \leq c \cdot g(n) $$

Now i know that from this we can conclude that:

$$ \lg f(n) = O(\lg g(n)) $$

But we cant conclude:

$$ 2^{f(n)} = O(2^{g(n)}) $$

Because there is a counter example: $f(n) = 2n, g(n) = n$

But i dont understand the logic, why it is working with $log$ but not with $2^x$?