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 proportional

For any two bases a and b, log base a and log base b are proportional, and in fact the proportionality constant is log_b a. We have

or to put it another way

As a corollary, O( log_a(x) ) = O( log_b(x) ) as x → ∞.. So if you say something is O(log n) and someone asks “log to what base?” the answer is “it doesn’t matter.”

Double logs are asymptotically proportional

Since log_a(x) is proportional to log_b(x), is log_a( log_a(n) ) proportional to log_b( log_b(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( log_a( log_a(x) ) )= O( log_b( log_b(x) ) ).

Note that the o(1) term goes to zero very slowly, like c / log (log x). If you’re proving a theorem in which x → ∞, you may be able to ignore this term. But for finite x, the o(1) term may be substantial, especially when a and b 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.

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, 5

for 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 posts

• Big-O and related notation
• Iterated logarithm