The Gateway to Computer Science Excellence
0 votes
34 views
Which is asymptotically larger: $lg(lg^*n)$ and $lg^*(lg n)$ ?
in Algorithms by Boss (41.9k points) | 34 views

1 Answer

+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 (35.7k points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,497 answers
195,490 comments
100,815 users