# 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 at 17:10 I am experimenting with using inverse Ackermann or the $\log^*$ (en.wikipedia.org/wiki/Iterated_logarithm) – stackoverflowuser95 Jan 28 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 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 at 16:43
$$f(n) = \frac{\log_2 \log_2 n}{\log_2 n}$$
@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 at 17:50