Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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^*$ ( – 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} $$

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.