27 views
Which is asymptotically larger: $lg(lg^*n)$ and $lg^*(lg n)$ ?
| 27 views

+1 vote

$lg^* n = min \{ i \geq 0 : lg^{(i)}n \leq 1 \}$

Iterated Logarithm or Log*(n) is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1.

$lg^*2 = 1$
$lg^*4 = 2$
$lg^*16 = 3$
$lg^*2^{16} = lg^*65536 = 4$
$lg^*2^{65536} = 5$

By the definition, $lg^* 2^m = 1 + log^* m$

let $n = 2^m$

$lg(lg^* n) = lg(lg^* 2^m) = lg (1 + lg^* m )$

and

$lg^*(lg \ n) = lg^*(lg \ 2^m) = lg^* m$

It is now obvious that $lg^* m$ grows faster than $lg (1 + lg^* m )$

we can say that,

$lg (1 + lg^* m ) = O( lg^* m)$

So,

$lg(lg^* n) = O(lg^*(lg \ n) )$

by Boss (35k points)

+1 vote
1
2