The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
27 views
Which is asymptotically larger: $lg(lg^*n)$ and $lg^*(lg n)$ ?
in Algorithms by Boss (41.4k points) | 27 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 (35k points)

Related questions

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,092 questions
55,276 answers
190,803 comments
86,086 users