 FACTOID # 26: Delaware is the latchkey kid capital of America, with 71.8% of households having both parents in the labor force.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > Iterated logarithm

In computer science, the iterated logarithm of n, written log*n, 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:

` function iterLog(real n) if n ≤ 1 return 0 else return 1 + iterLog(log(n)) ` Figure 1. Demonstrating log*4 = 2

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 a natural number. Graphically, it can be understood as the number of "zig-zags" needed in Figure 1 to reach the y-axis above the logarithm function.

The iterated logarithm is useful in analysis of algorithms and their computational complexity, appearing in the time and space complexity bounds of many algorithms such as:

The iterated logarithm is an extremely slowly-growing function, much more slowly than the logarithm itself; for all practical values of n (less than 265536, which is much more than the number of atoms in the universe), it does not exceed 5. Indeed, the only function used in complexity theory that grows more slowly is the inverse of the Ackermann function. For all practical purposes, the iterated logarithm may be considered to be a constant. Results from FactBites:

 Law of the iterated logarithm - Wikipedia, the free encyclopedia (176 words) In probability theory, the law of the iterated logarithm is the name given to several theorems which describe the magnitude of the fluctuations of a random walk. The original statement (1924) of the law of the iterated logarithm is due to A. One of the simpler forms of the law of the iterated logarithm can be stated as follows (Theorem 3.52 in Breiman).
 Some effects of trimming on the law of the iterated logarithm, Harry Kesten, Ross Maller (508 words) Hartman, P. and Wintner, A. On the law of the iterated logarithm. Maller, R. A functional law of the iterated logarithm for distributions in the domain of partial attraction of the normal distribution. Strassen, V. A converse to the law of the iterated logarithm.
More results at FactBites »

Share your thoughts, questions and commentary here
Press Releases | Feeds | Contact