Help logarithm function

[Wallstyouth]

Define lg*(x) to be the iterated logarithm function, which is the number of times that lg(x) can be applied until the result becomes nonpositive. For example, lg*(2) is 2 because lg(2) is 1 and lg(1) is 0. As another example, lg*(65536) is 5, because lg(65536) is 16, lg(16) is 4, lg(4) is 2, lg(2) is 1, and lg(1) is 0. Which of the following is true?


a) O(lg*(lg(x))) > O(lg(lg*(x))).
b) O(lg*(lg(x))) = O(lg(lg*(x))).
c) O(lg*(lg(x))) < O(lg(lg*(x))).

 

[Muting]

There is something I dont quite understand. Why lg(65536) is 16 rather than 11?Why lg(16) is 4 rather than 2? Do I miss something here?

 

[bigbadwolf]

There is something I dont quite understand. Why lg(65536) is 16 rather than 11?Why lg(16) is 4 rather than 2? Do I miss something here?

He's using 2 as a base (rather than e or 10).

 

[Muting]

To me, it is a). The informal reason is that lg*(x) goes down faster than lg(x). Does anyone have a more rigorous reasoning?

 

[Bastian Gross]

Hey Muting,
the iterated logarithm is an extremely slowly-growing function, much more slowly than the logarithm itself.
So I also would vote for a).

 

[Feixiang]

construct an "inverse" fn of lg*, := 2^^n, means 2^2^2^2....^2 (# of 2 is n);
so for 2^^(n-1)<x<=2^^(n), we have lg* (x)=n+1
lhs=lg*(lg(x)), lhs=n
rhs=lg(lg*(x)), rhs=lg(n+1)
at last solve this transcendental eq: n=lg(n+1)
we get n=1, i.e. x=2 is the symmetric point
x>2, lhs>rhs
x<=2, =