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$
1
  • $\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$ Commented Aug 27, 2017 at 0:57

3 Answers 3

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'$?

$\endgroup$
1
  • $\begingroup$ Ok, how about c' = 1 + |log(c)| and n0' = n0? $\endgroup$ Commented May 20, 2015 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, 𝑙𝑔(𝑓(𝑛))≠𝑂(𝑙𝑔(𝑔(𝑛))).

$\endgroup$
0
$\begingroup$

It is of course wrong. But why? Assume you have two functions 1 ≀ f(n) ≀ 2 for all n, and 1 ≀ g(n) ≀ 2 for all n. So f(n) = O (g(n)) with a constant c, 0.5 ≀ c ≀ 2.

But the logarithm of f(n), g(n) is between 0 and log 2. We can't say anything about the relation between log(f(n)) and log(g(n)) if all we know that both functions are between 0 and log 2. For example let g(n) = 1 + 1/n and f(n) = 2.

But the simplest counterexample is g(n) = 1 for all n, and f(n) = c for some constant c > 1, giving log (f(n)) = some constant > 0, and log(g(n)) = 0.

$\endgroup$

Your Answer

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

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