display | more...

log*(n) is the number of times you need to apply log to n to get a number < 1 (although since it's only ever used for complexity analysis, you can use any other constant instead of 1; 2 also seems popular).

If we take logarithms to base 2, log* is 1 in the range [1,2), 2 in the range [2,4), 3 in the range [4,16), 4 in the range [16,65536), 5 in the range [65536,265536). An n for which log*(n)=6 is unimaginable huge: considerably larger than 1018000(!)

Also known as the iterated logarithm, log* is the perfect example of a slowly-growing function. The log* of any sane number will be less than 5. If you write an algorithm that runs in O(log*n) time, you're doing pretty well.

For extra credit, compute the log* of Graham's Number.

Log in or register to write something here or to contact authors.