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 elsereturn 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 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.
Share your thoughts, questions and commentary here
Want to know more? Search encyclopedia, statistics and forums:
Press Releases |
The Wikipedia article included on this page is licensed under the
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m