If $f(n)$ is $O(g(n))$ and $g(n) > 1 + ε$ then $\log(f(n))$ is $O(\log(g(n)))$? 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!
 A: 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)).
$$
A: 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) $
