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

FACTS & STATISTICS    Advanced view

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)) 
Enlarge
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 »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
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