Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers

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|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^*$ (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
add comment

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

share|improve this answer
1  
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
add comment

Your Answer

 
discard

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.