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

$\endgroup$
1
  • $\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, 𝑙𝑔(𝑓(𝑛))≠𝑂(𝑙𝑔(𝑔(𝑛))).

$\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, privacy policy and cookie policy

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