Article 70D9S log log x

log log x

by
John
from John D. Cook on (#70D9S)

This post will include some simple but useful calculations.

Throughout this post, a and b are real numbers greater than 1.

All logs are proportional

For 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

loglog1.svg

or to put it another way

loglog2.svg

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 proportional

Since loga(x) is proportional to logb(x), is loga( loga(n) ) proportional to logb( logb(n) )? No, but sorta. A little algebra shows that

loglog6.svg

The second term on the right hand side goes to zero as x , and so we can write

loglog7.svg

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 logs

I 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.

loglog8.svg

So mixed logs are proportional to applying the log to the inner base twice.

Checking the algebra

The 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.
External Content
Source RSS or Atom Feed
Feed Location http://feeds.feedburner.com/TheEndeavour?format=xml
Feed Title John D. Cook
Feed Link https://www.johndcook.com/blog
Reply 0 comments