retagged by
489 views

1 Answer

Best answer
6 votes
6 votes

Lets substitute values: From definition $\log^* 2 = 1, \log^* 1 = 0.$

  $n= 2^{16}$ $n=2^{512}$ Relative Change
$\log^* n$ 4 5 5/4
$\log \log n$ 4 9 9/4
$(\log ^* n)!$ 24 120 5
$\log n$ 16 512 32
$(\log^*n)^n$ $4^{2^{16}}$ $5^{2^{512}}$ $> 5^{2^{496}}$
$(\log n)!$ 16! 512! ~512!

Since all the functions are monotonically increasing (continuously increasing) this relative comparison is enough to find the growth rate. So, options A and B are true here.


If the last option is difficult to calculate, we can take $n = 4$ and $n=8$ for it. We get

  $n=4$ $n=8$ Relative Change
$(\log^*n)^n$ $2^4 = 16$ $2^8$ 16
$(\log n)!$ 2 6 3
selected by

Related questions

0 votes
0 votes
2 answers
1
raja11sep asked Feb 13, 2022
842 views
Can anyone explain this?
0 votes
0 votes
1 answer
2
1 votes
1 votes
1 answer
3
Tridhara Chakrabarti asked Dec 24, 2017
585 views
Arrange the following functions in asymptotically increasing orderf1(n) = n0.999999 log nf2(n) = 10000000nPlease explain your solution. Thanks