# Is $n\log_{2}\log_{2}n = O(n\log_{3}\log_{3}n)$?

I've proven that $$n\log_{2}\log_{2}n = \Omega (n\log_{3}\log_{3}n)$$ but is $$n\log_{2}\log_{2}n = O(n\log_{3}\log_{3}n)$$ also true? Looks like it's not and actually $$n\log_{2}\log_{2}n = \omega(n\log_{3}\log_{3}n)$$. A problem of CLRS led me ask this.

• We have "$\log_{a}b$" or "$\log_{a}(b)$" for $\log$ function with base "$a$" and argument "$b$", but what is $$\log_{a}^{b}$$ Is this power of $\log$? if yes, then what is argument? fix, please. Aug 12 '21 at 12:07
• @zkutch It is just a logarithm with base 2 and argument $\log(n)$ and the other one is a logarithm as well. I'll fix it.
Aug 12 '21 at 12:19
• math.stackexchange.com/a/37379/890149 does this answer your question? Aug 12 '21 at 12:47
• @nirshahar Yes. My question got solved. The idea of changing the base of the logarithm and computing the limit had stricken my mind but I was lazy to compute the limit! I computed it and it got solved.
Aug 12 '21 at 15:46

Yes, also we can get a tighter result that show us $$n\log_2\log_2n=\Theta(n\log_3\log_3n)$$ .Suppose $$c',c''>0$$ is a constant, hence
$$\lim_{n\to\infty}\frac{n\log\log n}{n\log_{3}\log_{3}n} = \frac{n\log\log n}{cn\frac{\log\left(\frac{\log n}{\log 3}\right)}{\log 3}}=c'$$ Also $$\lim_{n\to\infty}\frac{n\log_{3}\log_{3}n}{n\log\log n} = \frac{cn\frac{\log\left(\frac{\log n}{\log 3}\right)}{\log 3}}{n\log\log n}=c''.$$
$$n\log_2\log_2n=\Theta(n\log_3\log_3n).$$