Which of the growth rates (log * n) and log * (log n) is faster?

Question

As n gets larger, of the two functions, log * (log n) and log (log * n) will be faster?

Here the log * function is the iterated logarithm defined here:

I suspect it's the same thing, just written differently, but is there any difference between them?

Answer 1

log * n is the iterative logarithm , which for large n is defined as

log* n = 1 + log*(log n) 

Therefore, log * (log n) = (log * n) - 1, since log * is the number of times you need to apply the log to a value before it reaches some fixed constant (usually 1). Running another log at first simply removes one step from the process.

Therefore, log (log * n) will be much smaller than log * (log n) = log * n - 1, since log x <x - 1 for any sufficiently large x.

Hope this helps!