3
$\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!

|cite|improve this question
$\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.