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 |