1
$\begingroup$

I read this answer

But functions in my case seems to be complicated to me..


Which of the following functions asymptotically grows the fastest as $n$ goes to infinity?

$(\log \log(n))!$

$(\log\log(n))^{\log(n)}$

$(\log\log(n))^{\log\log\log(n)}$

$(\log(n))^{\log\log(n)}$

$2^{\sqrt{\log\log(n)}}$


for example take the first and second function that are

$f(n) = (\log\log(n))!$

$g(n) = (\log\log(n))^{\log(n)}$

now calculating

$$\lim_{n \to \infty} \frac{f(n)}{g(n)}$$

$f(n)$ it's derivative can't be calculated.

Then how can I tell which function asymptotically grows fastest ?

The answer given in the book is $(\log\log(n))^{\log(n)}$

$\endgroup$
2
  • $\begingroup$ Welcome to MSE. Your formatting will look nicer if you write \log instead of log. (Same goes for \sin, \max, etc.) $\endgroup$
    – saulspatz
    Aug 31 '18 at 9:43
  • $\begingroup$ I suppose the first is $f(n)=\log\bigl(\log(n!)\bigr)$. $\endgroup$
    – Bernard
    Aug 31 '18 at 10:19
2
$\begingroup$

Take logarithms. To compare the second with the first, for example, ee have $$ \log((\log\log n)^{\log n}) = \log n \cdot\log\log\log n \tag{1}$$ On the other hand, we know that $\log(x!) \sim x\log x,$ so that $$ \log(\log \log n)!) \sim \log\log n \cdot \log\log\log n\tag{2} $$ Comparing $(1)$ and $(2)$, we see that $(1)$ grows much faster.

It looks to me like the fourth one is the biggest, just doing it in my head.

$\endgroup$
3
  • $\begingroup$ What is $\log(x!)$ if $x$ is not a positive integer? $\endgroup$
    – Bernard
    Aug 31 '18 at 11:09
  • $\begingroup$ @Bernard I assume he's talking about the gamma function $\endgroup$
    – saulspatz
    Aug 31 '18 at 11:10
  • $\begingroup$ @saulspatz use of stirling approximation was a nice idea. $\endgroup$ Aug 31 '18 at 15:24

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.