# If $f(n) \in O(g(n))$, and $g(n) \geq 2$ then $\log{f(n)} \in O(\log{g(n)})$?

I need your help in following problem

Using the definition of $O$ symbolism, show that given two functions $f(n)$ and $g(n)$ that $g(n)\geq2$ is true $f(n)=Ο(g(n))$, then it would also be true that $\log{f(n)}=Ο(\log{g(n)})$. The $g(n)\geq2$ fact, means that $\log{g(n)}\geq1$. Is this true if we don’t have as a fact that $g(n)\geq2$?

-
How far have you got by yourself? And what does $g(n) \ge 2$ mean? $\forall n : g(n) \ge 2$? $\forall n > 0: g(n) \ge 2$? $\exists N : \forall n > N : g(n) \ge 2$? Something else? – Peter Taylor Feb 8 '12 at 12:56

Let us assume that $f(n)=O(g(n))$ and let us see how far we can go towards proving that $\log f(n)=O(\log g(n))$. First, since $f(n)$ and $g(n)$ are positive, $f(n)=O(g(n))$ means exactly that there exists some finite $N$ and $C$ such that $f(n)\leqslant Cg(n)$ for every $n\geqslant N$. Thus, for every $n\geqslant N$, $\log f(n)\leqslant\log g(n)+\log C$.

A first problem here is that $f(n)$ could be positive but very small. For example $f(n)=1/n$ and $g(n)=5$ for every $n$ yields $f(n)=O(g(n))$ but $\log f(n)=-\log n$ is not $O(\log g(n))=O(1)$.

Assume thus that $f(n)\geqslant c$ for every $n\geqslant1$, with $c\gt0$. Then $g(n)\geqslant2$ hence $\log g(n)\geqslant\log2\gt0$ and $\log f(n)\geqslant\log c+\log2-\log g(n)$ for every $n\geqslant1$. In the other direction, for every $n\geqslant N$, $\log f(n)\leqslant\log g(n)+\log C$.

Exercise: Assume that $y_n-a\leqslant x_n\leqslant y_n+a$ and $y_n\geqslant c$ with $c\gt0$ and $a$ finite. Then $x_n=O(y_n)$.

Finally, if $f(n)=O(g(n))$ and $f(n)\geqslant c$ for some $c\gt0$ and $g(n)\geqslant2$ for every $n$ large enough, then $\log f(n)=O(\log g(n))$.

Edit: The hypothesis that $g(n)\geqslant2$ is there to make sure that $g(n)$ stays away from $1$. One needs it to avoid relying on the properties of the logarithm near $1$. For a case where things go awry, assume for example that $f(n)=1+a(n)$ and $g(n)=1+b(n)$ with $a(n)\to0$ and $b(n)\to0$. Then $f(n)=O(g(n))$ but $\log f(n)\sim a(n)$ and $\log g(n)\sim b(n)$ hence the relative behaviour of $\log f(n)$ and $\log g(n)$ can be about anything. On a related note, $f(n)\geqslant c$ with $c\gt0$ and $f(n)=O(g(n))$ implies that $g(n)\geqslant c'$ with $c'\gt0$.

-
Thanks for your answer. I need to ask you something more. Is this true if we don’t have as a fact that g(n)≥2??? What is the clue that "g( n) >=2" is telling us? – Vasilis Feb 8 '12 at 13:43
See Edit.   – Did Feb 8 '12 at 14:45
@Peter: No.  – Did Feb 8 '12 at 14:49
Are you working with a different definition of $O(g(n))$ than the one given in the first paragraph, then? Because it's certainly the case that $\forall n \ge 1 : -\log n < 1$ – Peter Taylor Feb 8 '12 at 14:56
@Peter: Why are you deleting your comments? – Did Feb 8 '12 at 15:23

can we prove like this :

$f(n) \le c g(n)$ (given)

$f(n) \le (c_1^{c_2}) g(n),\ c_1>0,\ c_2<0$ taking log on both sides,

$\log(f(n)) \le c_2 \log c_1 + \log(g(n))$

Since $c_2<0$, $log (f(n) )$<=$log(g(n))$, therefore

$log f(n) = O( log(g(n) )$

is this proof correct ?

-
You went from $f(n) \le c g(n)$ to $f(n) \le g(n)$. Impossible logic. – Erick Wong Sep 17 '12 at 2:11
@Erick Wong I too had a hunch this method is wrong but could you please tell me which step is wrong ? – rishabh Sep 17 '12 at 9:18
Try tracing through your argument with $c=1/2$ and find the first statement which is a lie. – Erick Wong Sep 17 '12 at 12:07