In computer science, the iterated logarithm of n, written log* n (usually read "log star"), is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1. The simplest formal definition is the result of this recursive function:
On the positive real numbers, the continuous super-logarithm (inverse tetration) is essentially equivalent:
but on the negative real numbers, log-star is 0, whereas for positive x, so the two functions differ for negative arguments.
In computer science, lg* is often used to indicate the binary iterated logarithm, which iterates the binary logarithm instead. The iterated logarithm accepts any positive real number and yields an integer. Graphically, it can be understood as the number of "zig-zags" needed in Figure 1 to reach the interval on the x-axis.
Mathematically, the iterated logarithm is well-defined not only for base 2 and base e, but for any base greater than .
Read more about Iterated Logarithm: Analysis of Algorithms, Other Applications
Famous quotes containing the word iterated:
“The customary cry,
‘Come buy, come buy,’
With its iterated jingle
Of sugar-bated words:”
—Christina Georgina Rossetti (1830–1894)