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

4

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