# For what $f(n)$ does $O(f(n) \log n)=O(\log\log n)$?

$k=f(n)$.

Given $O(k \log_2 n)$, what function $f$ of $n$ would be needed for it to equal $O(\log_2 \log_2 n)$?

(where $k \in n \in \mathbb{Z}^+$)

-

Even if $k$ is a constant $f(n) \log n \in \omega(\log \log n)$. Hence if you are looking for a monotonously growing function I only see the constant zero function.

-
In that case; what's the slowest growing function I can use for computing $k$ in this equation? –  stackoverflowuser95 Jan 28 '13 at 17:10
I am experimenting with using inverse Ackermann or the $\log^*$ (en.wikipedia.org/wiki/Iterated_logarithm) –  stackoverflowuser95 Jan 28 '13 at 17:30
As far as I know there is no "slowest growing function" (apart from constants) as you can always take the log of it and make it even slower. Or take the inverse Ackermann and apply itself again, then log, then inverse Ackermann... it always gets slower and slower. But this does not solve the original problem. –  user1965813 Jan 29 '13 at 6:20
It doesn't solve the original problem, however it does dramatically reduce the total asymptotic complexity of this problem I'm solving. –  stackoverflowuser95 Jan 29 '13 at 16:43

$$f(n) = \frac{\log_2 \log_2 n}{\log_2 n}$$

-
what do you want to compute? I don't understand... –  Emanuele Paolini Jan 28 '13 at 17:47
Thanks, just realised WolframAlpha doesn't recognise Big Oh. So I had to confirm by hand (yay!). Thanks, that seems to be the function I was looking for :) –  stackoverflowuser95 Jan 28 '13 at 17:49
@stackoverflowuser95 Then why did you specify $k \in \mathbb Z^+$? This function will always be between $0$ and $1$, at least for $n > 2$, and it decreases toward $0$. –  Erick Wong Jan 28 '13 at 17:50
Are we even considering decreasing functions? –  user1965813 Jan 30 '13 at 7:40