1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – zkutch
    Aug 12 '21 at 12:07
  • $\begingroup$ @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. $\endgroup$
    – Emad
    Aug 12 '21 at 12:19
  • $\begingroup$ math.stackexchange.com/a/37379/890149 does this answer your question? $\endgroup$
    – nir shahar
    Aug 12 '21 at 12:47
  • $\begingroup$ @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. $\endgroup$
    – Emad
    Aug 12 '21 at 15:46
2
$\begingroup$

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''.$$

Note that constant factor have no effect on the growth rate of asymptotic functions, therefore

$$n\log_2\log_2n=\Theta(n\log_3\log_3n).$$

$\endgroup$
1
  • $\begingroup$ I also solved it using the limit but I did some more calculations to show that indeed the limit exists: Things like the L'Hopital's rule. $\endgroup$
    – Emad
    Aug 12 '21 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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