# How is $O(\log(\log(n)))$ also $O( \log n)$?

How is $O(\log(\log(n)))$ also $O( \log n)$?

I have seen this result somewhere with this but I still didn't quite understand how this is true. This would also help me compute Big Omega of the same function.

• What is probably meant is that each function that is $O(\log \log n)$ is also $O(\log n)$. But note that $\log n$ is in the latter but not the former (as $n \to \infty$). – D Poole Sep 7 '14 at 23:04

Suppose $f(n) = O(\log\log n)$, and we want to prove that $f(n) = O(\log n)$.

Assume $f(n)$ is a positive function. By the definition of the big $O$ notation, $f(n) = O(\log\log n)$ implies that there exists a $N_0$ and a positive constant $k$ such that $$f(n) \leq k\cdot \log\log n, \ \forall n \geq N_0$$

Since $\log\log n \leq \log n$ for sufficiently large $n$, there must exist a $N_1$ such that $$f(n) \leq k \cdot \log n, \ \forall n \geq N_1$$ thus $f(n) = O(\log n)$.

This is because, if $n$ is large enough, $\lvert f\rvert\le K\log(\log n)$ for some constant $K$ and $\log x \le x$ for all $x$.

More generally, if $f=O(g)$ and $g=O(h)$ then $f=O(h)\,$ $\,(O(O(h))=O(h)$).

Firstly, we assume all functions are nonnegative. $f(n)$ is $O(g(n))$ if $$\lim_{n\rightarrow \infty} \sup \frac{f(n)}{g(n)} \leq K<\infty\quad(1)$$ where the finite constant $K$ is independent of $n.$ Thus if $f(n)=O(g(n))$ and $h(n)\leq f(n)$ for $n$ large enough, then $h(n)=O(g(n)).$

If $K=0$ then we say $f(n)=o(g(n))$ but it still holds that $f(n)=O(g(n)).$

If $f(n)=O(g(n))$ and $g(n)=O(f(n))$ then $f(n)=\Theta(g(n))$ i.e., they are the same order up to a finite constant, for $n$ large enough.

• Why should $\dfrac{f(n)}{g(n)}$ have a limit? – Bernard May 30 '15 at 8:18
• @Bernard, thanks for spotting the mistake. – kodlu May 30 '15 at 9:06