Is $\log(\log(n)) = O(\log(n))$?

Question

I need to prove or disprove that $\log(\log(n)) = O(\log(n))$.

I've tried the following:

$\log(\log(n)) \le c * \log(n)$

$\log(\log(n)) \le \log(n^c)$

$\log(n) \le n^c$

But I got stuck, and I couldn't figure out where to go.

Answer 1

You can use $c=1$: you just have to check that there is an $n_0$ such that $\log(\log n)\le\log n$ whenever $n\ge n_0$. The log function is monotone increasing, so this amounts to checking that $\log n\le n$ or, if you prefer, that $n\le e^n$.

Answer 2

By substitution, $\;\log(\log n)=o(\log n)$. And $$f=o(g)\implies f=O(g).$$