303 views

1 Answer

1 votes
1 votes

$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) )$

Related questions

1 votes
1 votes
0 answers
1
akash.dinkar12 asked Apr 4, 2019
170 views
Is the function $\lceil$ $lg$ $n$ $\rceil$$!$ polynomially bounded ? Is the function $\lceil$ $lg$ $lg$ $n$ $\rceil$$!$ polynomially bounded ?
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Jun 27, 2019
307 views
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.