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

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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