• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

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))).
 
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?
 
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
    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).
 
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, =
 
Top