1

I'm having trouble with the following exercise:

Prove that if $f$ and $g$ are positive functions, $f(n)$ is $O(g(n))$ and $g(n) > 1 + ε$ for sufficiently big $n$, then $\log(f(n))$ is $O(\log(g(n)))$.

This is what I've done:

$f(n)$ is $O(g(n)) \implies \exists n_0$ such that for all $n>n_0 $ it holds that $f(n) < cg(n) $ for some positive constant $c \implies \log (f(n)) < \log(cg(n)) = \log(c) + \log(g(n)) $

That's where I'm stuck. I'd appreciate any suggestions!

emacs drives me nuts
  • 10,390
  • 2
  • 12
  • 31
lbal
  • 311
  • You can look in two directions: one $g$ bounded from below and second $f$ have limit infinity. – zkutch Aug 20 '22 at 00:12

2 Answers2

1

As you correctly wrote, $f(n)=O(g(n))$ means $$ \exists c>0, \exists n_0>0, \forall n\ge n_0, \quad f(n)\le cg(n). $$ Since $\log(\cdot)$ is strictly increasing then $$ \exists c>1, \exists n_0>0, \forall n\ge n_0, \quad \log(f(n))\le \log(cg(n))=\log(c)+\log(g(n)). $$ Note that you can choose $c>1$. In addition, by hypothesis, $$ \exists \varepsilon_0>0, \exists n_1>0, \forall n\ge n_1, \quad g(n) \ge 1+\varepsilon_0, $$ i.e., $\log(g(n))\ge \log(1+\varepsilon_0)>0$ for all $n\ge n_1$. Then you have $$ \exists n_2>0, \forall n>n_2, \quad c+\log(g(n))\le c\log(g(n)). $$

What you would like to prove is: $$ \exists c^\prime>0, \exists n_3>0, \forall n\ge n_3, \quad \log(f(n))\le c^\prime\log(g(n)). $$ Now it is enough to set $n_3:=\max\{n_0,n_1,n_2\}$ and $c^\prime:=\log(c)$. Indeed, for all $n\ge n_3$, you have $$ \log(f(n)) \le \log(c)+\log(g(n))=c^\prime+\log(g(n))\le c^\prime \log(g(n)). $$

Paolo Leonetti
  • 15,423
  • 3
  • 24
  • 57
  • Thanks for your answer! I'm having trouble understanding why c+log(g(n)) <= clog(g(n)). Can you help me with that? The rest is super clear. – lbal Aug 20 '22 at 00:39
1

I bring proof for both ways mentioned in comment.

1.

$\text{For } \forall C > 0, C = \text{Const.} $ and $ \forall f $ with $\lim\limits_{n\to\infty}f(n)=+\infty$ we have $$ O(f(n)) +C = O\big(f(n)+C\big) =O(f(n))$$ Proof: Let me show one from brought $4$ subset operations. Suppose we want to prove $O(f(n)) +C \subset O\big(f(n)\big)$. Taking $\phi \in O(f(n)) +C$ we have, that $\exists \psi(n) \in O(f(n))$ s.t. $\phi = \psi + C$. So $\exists A>0, N\in\mathbb{N},\forall n>N,\psi(n) \leqslant A \cdot f(n)$. From here $$\phi(n) = \psi(n) + C \leqslant A \cdot f(n) + C=f(n)\left(A+\frac{C}{f(n)}\right)\leqslant (A+1) \cdot f(n)$$ because we can consider $\frac{C}{f(n)}<1.$

2.

if $ \min(f)>0$, then $\forall C>0$ $$ O(f(n)) +C = O(f(n)) = O(f(n)+C) $$ Proof: assume $ \varphi \in O(f) + C $, then $ \exists \psi \in O(f) $ s.t. $ \exists A > 0, \exists N \in \mathbb{N}, \forall n > N, \ \psi(n) \leqslant A \cdot f(n) $ and $ \varphi = \psi + C $. Then we have $$ \varphi(n) = \psi(n) + C \leqslant A \cdot f(n) + C = \left( A + \dfrac{C}{f(n)}\right) \cdot f(n) \leqslant \left( A + \dfrac{C}{\min(f)}\right) \cdot f(n) =\\ = B \cdot f(n) $$

where $ B= A + \dfrac{C}{\min(f)} $ and $ n > N$. So, $ O(f) +C \subset O(f) $

zkutch
  • 13,410