Prove that $\log \log y = \mathcal{o}(\log y) + \mathcal{O}(1)$. I just wanted some help to prove that 
$$\log_2 \log_2 y = \mathcal{o}(\log_2 y) + \mathcal{O}(1),$$ when $y = f(n) \in \mathcal{O}(n)$ and $y > 4$. 
Thanks!
 A: To make things clear, I think that you are trying to show that for all sequences $u_n>4$, there exist a sequence $a_n\to 0$ and a constant $b$ such that for all $n$,
$$\lg \lg u_n\le a_n\lg u_n + b$$
(The hypothesis $u_n=O(n)$ is not useful since the difficult cases are when the growth is slow, not when it is fast.)

The result is of course true when $u_n$ is non-decreasing (since it is either bounded or diverging).
But the result is false in the general case.
Let $u_n = 5+n-\lfloor \sqrt n\rfloor^2$.
We have $$u_n=\ 5,\ \ 5,6,7,\ \ 5,6,7,8,9,\ \ 5,6,7,8,9,10,11,\ \ \dots$$
so that it is possible to extract an arbitrarily slowly growing sequence from $u_n$.
Suppose the result is true and consider the subsequence $u_{\phi(n)}$ of $u_n$ formed by the elements where
$$\frac{\lg u_n}{\lg \lg u_n}<\frac{1}{2a_n}$$
Because the right hand side diverges and $u_n$ hits each integer infinitely many times, each integer will eventually be reached by $u_{\phi(n)}$ so that it is not bounded.
We have
$$\lg\lg u_{\phi(n)}\le a_n\lg u_{\phi(n)} + b < \tfrac 12 \lg\lg u_{\phi(n)} + b$$
$$\lg\lg u_{\phi(n)} < 2b$$
But this contradicts the fact that $u_{\phi(n)}$ is not bounded. So the result is false in general.

EDIT: I didn't see this, but in the comments Siminore asked a very different question:

For all $\varepsilon>0$, there is a constant $C_\varepsilon$ such that for all $y\ge 2$,
  $$\lg\lg y \le \varepsilon\lg y + C_\varepsilon$$

This version is true: $\lg\lg y/\lg y\to 0$ as $y\to+\infty$, so that there is an $M_\varepsilon$ such that for $y\ge M_\varepsilon$, we have $\lg\lg y/\lg y<\varepsilon$. But the continuous function $\lg \lg y - \varepsilon\lg y$ is bounded on $[2,M_\varepsilon]$, so calling $C_\varepsilon$ its maximum finishes the proof.
The reason why this works is twofold: $\varepsilon$ does not need to go to 0 as $y\to+\infty$, and $C_\varepsilon$ is allowed to diverge as $\varepsilon\to 0$ (in the first version, $b$ is fixed for obvious reasons).
