Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thanks for your help

share|improve this question
2  
If this is homework, please tag it as such. Also, 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
add comment

2 Answers

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$.

share|improve this answer
    
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
1  
@Peter: Why are you deleting your comments? –  Did Feb 8 '12 at 15:23
show 8 more comments

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 ?

share|improve this answer
1  
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
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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