retagged by
2,518 views

2 Answers

2 votes
2 votes
x lg* x
(−∞, 1] 0
(1, 2] 1
(2, 4] 2
(4, 16] 3
(16, 65536] 4
(65536, 265536] 5

for n>4 lg*(lg(n)) is asymtotically greater than lg(lg*(n)).table is from wikipedia

2 votes
2 votes

log*n is called the iterated logarithm of n, defined as the count of how many times you apply the logarithm function iteratively such that the value is less than or equal to 1.
eg, log*16=3
The recurrence relation is as follows : 
log*n = 0 , if n<=1
         = 1 + log*(log n) , if n>1
log 16
= 1+log*(log16) = 1+log*4
           = 1+1+log*(log4) = 1+1+log*2
           = 1+1+1+log*(log2) = 1+1+1+log*1 = 1+1+1+0 = 3
                   
Notice that the iterated logarithm function grows at an extremely slower rate compared to logarithm function. 
For a very large value of n, log*n will be a very small value compared to logn.
 eg, for n=1024, log n=10 and log*n=4 
       
     n= 265536 , log n = 65536 and log*n=5

Also, log*n will take one less iteration on log*(logn) [ Look at the recurrence relation ]
log*n -1 = log*(logn)
Consider log*n=x,
log(log*n) = log x
log*(log n) = log*n - 1 = x - 1 
clearly, log*(log n) is asymptotically larger than log(log*n)



                 

Related questions

0 votes
0 votes
1 answer
1
Neha_16 asked Apr 27, 2018
5,806 views
Use a recursion tree to give an asymptotically tight solution to the recurrenceT(n) =T(an)+T((1-a)n)+cn, where a is constant in the range 0<a<1 and c>0 is also a constant...
0 votes
0 votes
0 answers
2
Aarvi Chawla asked Jun 11, 2018
246 views
Indicate for pair of expressions (A,B) whether A is O, o, Ω, ω or of B?A = lg(n!)B = lg(n^n)
0 votes
0 votes
0 answers
3
0 votes
0 votes
1 answer
4
akash.dinkar12 asked Jun 28, 2019
450 views
Obtain asymptotically tight bounds on $lg\ (n!)$ without using Stirling’s approximation. Instead, evaluate the summation $\sum_{k=1}^{n} lg\ k$.