# How can I prove big-oh relation between $\log_2(\log_2 n)$ and $\sqrt{\log_2 n}$

How can I prove big-O relation between $f=\log_2(\log_2 n)$ and $g=\sqrt{\log_2 n}\,$?

I want to find the constants, $c, N$ such that $\ g(x) \leq cf(x)$ for all $x>N$.

-
First you can find when $\log_2\log_2 N=\sqrt{\log_2 N}$. What happens if you take $x>N$ after that? – Ian Coley Mar 20 '13 at 16:36
A useful result, if $\lim_{n\to \infty} \frac{g(n)}{f(n)}=a$, then $g=O(f)$. – Mhenni Benghorbal Mar 20 '13 at 16:49
As an additional comment, you need only check the relation between $\log_2x$ and $\sqrt x$. You may solve for $c,N'$ in this case let $N=2^{N'}$. – Ian Coley Mar 20 '13 at 16:53
You can't. Did you mean $f(x) \le c g(x)$? – Aryabhata Apr 3 '13 at 9:06
@FrankMcGovern I fail to see the point of solving $\log_2x=\sqrt{x}$. – Did Apr 3 '13 at 9:26

The derivative of the usual logarithm function is less than $1$ on $(1,+\infty)$ hence $\ln x\leqslant x-1$ on $x\geqslant1$. This implies $\log_2x\leqslant2x$ on $x\geqslant1$. Since $\log_2x=2\log_2\sqrt{x}$, $\log_2x\leqslant4\sqrt{x}$ on $x\geqslant1$.
Appplying this to $x=\log_2n$, one sees that $f(n)\leqslant4g(n)$ for every $n\geqslant2$.