I guess this is true, because log is a strictly increasing function, but how do I prove it formally?
I tried something like:
Let $f(n)$ and $g(n)$ be monotonically increasing functions, $c \in \mathbb{R}$ and $n_0 \in \mathbb{N}$, such that $0 \leq f(n) \leq c g(n)$, for all $n \geq n_0$. We must find $c'$ and $n_0'$ such that $$\log(f(n)) \in \{h(n) \mid 0 \leq h(n) \leq c' \log(g(n)), \forall n \geq n_0'\}\,.$$
I got as far as $$f(n) \leq c g(n) \implies \log(f(n)) \leq \log(c g(n)) = \log(c) + \log(g(n))\,.$$
Then I got stuck.
Thanks in advance!
log()
is a strictly increasing function. In that case,2^n
is also a strictly increasing function but its not true for2^n
. $\endgroup$ – Severus Tux Aug 27 '17 at 0:57