4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ It is true. But not because log() is a strictly increasing function. In that case, 2^n is also a strictly increasing function but its not true for 2^n. $\endgroup$ – Severus Tux Aug 27 '17 at 0:57
2
$\begingroup$

You need to find a number $n'_0,c'$ such that

$$\log(c) + \log(g(n)) \le c' \log(g(n)) \text{ for all $n \ge n'_0$,}$$

and such that $n'_0 \ge n_0$.

So, see what you can find. Note that it's ok for $n'_0,c'$ to depend on $c$ and on $g(\cdot)$.

Hint: If you can find $n'_0,c'$ such that $\log(c) \le \log(g(n'_0))$, does anything good happen? Can you find such a $n'_0,c'$?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ok, how about c' = 1 + |log(c)| and n0' = n0? $\endgroup$ – matheuscscp May 20 '15 at 1:04
1
$\begingroup$

If we assume all functions are nonnegative and strictly increasing, then I think this relationship is true, however if we take the following cases: Let $f(n) = 2$ and $g(n) = 1$ then clearly 𝑓(𝑛)=𝑂(𝑔(𝑛)), however, 𝑙𝑔(𝑓(𝑛))=1,𝑙𝑔(𝑔(𝑛))=0, therefore, 𝑙𝑔(𝑓(𝑛))≠𝑂(𝑙𝑔(𝑔(𝑛))).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.