Consider
$$ E(n)=\log_2\left(\log_2 (4)\right) +\log_2\left(\log_2 (5)\right) ... \log_2\left(\log_2 (n)\right) $$
This is equal to
$$E(n)= \log_2\left(\log_2 (4)*\log_2(5)*\log_2(6) ... \log_2(n) \right) $$
I want to find the two tightest possible functions A, B such that
$$ A(n) = O(E(n)) , E(n) = O(B(n))$$
For a basic start I noted that
$$E(n) \le log_2(4) + log_2(5) ... log_2(n) \le log_2(2) + log_2(3) ... log_2(n) \le log_2(n!) = O(n \log(n))$$
And clearly
$$1 + 1 + 1 ... 1 \ (n \ times) < E(n)$$
Thus $$ n = O(E(n)), E(n) = O(n \log(n))$$
But I want to get a much tighter bound than this. I hypothesize that
$$E(n) = O(n \log(\log(n))$$
But a method of proof escapes me at the moment. Any ideas??
Your sum $E(n)$ is a Riemann sum for an integral of an increasing function; in particular, $$ \int_3^n \log_2(\log_2 x)\,dx < E(n) < \int_4^{n+1} \log_2(\log_2 x)\,dx. $$ The function $\log_2(\log_2 x)$ has a nearly elementary antiderivative (that can be found by integrating by parts): $$ \int \log_2(\log_2 x)\,dx = x\log_2(\log_2 x) - \frac{\mathop{\rm li}(x)}{\log 2}, $$ where the logarithmic integral li$(x)$ is defined by $$ \mathop{\rm li}(x) = \int_2^x \frac{dt}{\log t}. $$ Therefore $$ n\log_2(\log_2 n) - \frac{\mathop{\rm li}(n)}{\log 2} + O(1) < E(n) < (n+1)\log_2(\log_2 (n+1)) - \frac{\mathop{\rm li}(n+1)}{\log 2} + O(1), $$ which easily implies $$ E(n) = n\log_2(\log_2 n) - \frac{\mathop{\rm li}(n)}{\log 2} + O(\log\log n). $$