log log x
This post will include some simple but useful calculations.
Throughout this post, a and b are real numbers greater than 1.
All logs are proportionalFor any two bases a and b, log base a and log base b are proportional, and in fact the proportionality constant is logb a. We have
or to put it another way
As a corollary,O( loga(x) ) = O( logb(x) ) as x . So if you say something is O(logn) and someone asks log to what base?" the answer is it doesn't matter."
Double logs are asymptotically proportionalSince loga(x) is proportional to logb(x), is loga( loga(n) ) proportional to logb( logb(n) )? No, but sorta. A little algebra shows that
The second term on the right hand side goes to zero as x , and so we can write
The double logs to different bases are not proportional, but they become more nearly proportional as x grows larger. As a corollary, O( loga( loga(x) ) )= O( logb( logb(x) ) ).
Note that the o(1) term goes to zero very slowly, like c / log (logx). If you're proving a theorem in which x , you may be able to ignore this term. But for finitex, theo(1) term may be substantial, especially when a andb are far apart.
Mixed logsI was reading a paper the other day that frequently iterated logs to different bases, which was kind of confusing. The mix could be eliminated with the following equation.
So mixed logs are proportional to applying the log to the inner base twice.
Checking the algebraThe algebra above is a little tedious and error-prone. Here's some code to give complementary validation of the calculations.
from math import log# Note that log(x, b) = log_b(x)a, b = 3, 5for x in [9, 29, 2025]: u = log(log(x, b), b) / log(log(x, a), a) v = log(a, b) + log(log(a, b), a)*log(a, b) / log(log(x, a), a) assert( abs(u - v) < 1e-15 ) u = log(log(x, b), a) v = log(log(x, b), b) * log(b, a) assert( abs(u - v) < 1e-15 )Related postsThe post log log x first appeared on John D. Cook.