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

79 Views Asked by At

$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}^+$)

2

There are 2 best solutions below

4
On BEST ANSWER

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.

4
On

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