# Help logarithm function

#### Wallstyouth

##### Vice President
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?

#### Attachments

• ite_log.JPG
33.1 KB · Views: 22

#### Bastian Gross

##### German Mathquant
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, =

Replies
0
Views
959
Replies
0
Views
508
Replies
2
Views
966
Replies
7
Views
2K
Replies
0
Views
944