0
$\begingroup$

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

  • 2
    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?2012-02-08

1 Answers 1

3

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

  • 0
    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?2012-02-08
  • 0
    See Edit. $ $ $ $2012-02-08
  • 0
    @Peter: No. $ $2012-02-08
  • 0
    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$2012-02-08
  • 0
    @Peter: The fact that $a(n)\leqslant b(n)$ is related to the assertion that $a(n)=O(b(n))$ only for positive sequences $(a(n))$ and $(b(n))$. Please check [the definition](http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition).2012-02-08
  • 1
    @Peter: Why are you deleting your comments?2012-02-08
  • 0
    Because not everyone who comes along here needs to read the whole chain. Besides, I was expecting an edit I made to add the absolute values from the definition you link to be accepted, and then it would have made no sense. Why did you reject it?2012-02-08
  • 0
    Because absolute values are not needed there.2012-02-08
  • 0
    You're trying to have your cake and eat it. Either the absolute values are part of the definition, so you should include them when you state the definition, or they aren't, so you can't rely on them in the second paragraph.2012-02-08
  • 0
    @Peter: No. Please read: *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$*. Anything wrong with this? This is **not** the (general) definition of big-O, but what this definition gives when applied to positive sequences. The second paragraph examines whether the (real valued) sequences $\log f$ and $\log g$ are or are not such that $\log f=O(\log g)$ (in the example, they are not). In both cases, no originality, nothing but the pure and canonical definition of big-O.2012-02-08
  • 0
    Ok, if you add a justification for assuming $f$ and $g$ to be positive then that covers the bases. BTW I think you need to change the bound on $c$ to be $c > 1$ or your example of $f(x) = x^{-1}$ can be changed to $f(x) = x^{-1} + c$ for small $c$ and the conclusion again fails to hold.2012-02-08
  • 0
    @Peter: Do you think $f$ and $g$ can be anything else than positive when the question asked is about $\log f$ and $\log g$? // *and the conclusion again fails to hold*... No, $c+1/n=O(2)$ for every real number $c$ and $\log(c+1/n)=O(\log2)$ for every positive $c$. // Are you a troll?2012-02-08
  • 0
    No, but it's still convenient for the reader to tell them why a statement isn't just pulled from thin air. And no, but I haven't had any coffee today. Aargh.2012-02-08