Menu
I have come across the term O(log* N) in a book I'm reading on data structures. What does log* mean? I cannot find it on Google, and WolframAlpha doesn't understand it either.
775
A logarithm is the power to which a number must be raised in order to get some other number (see Section 3 of this Math Review for more about exponents). For example, the base ten logarithm of 100 is 2, because ten raised to the power of two is 100: log 100 = 2.
Logarithms are the inverse of exponents. A logarithm (or log) is the mathematical expression used to answer the question: How many times must one “base” number be multiplied by itself to get some other particular number? For instance, how many times must a base of 10 be multiplied by itself to get 1,000?
In algebra, “log” is short for “logarithm.” Logarithms are the opposites, or inverses, of equations involving exponents, like y = x^3. In their simplest form, logs help to determine how many of one number must be multiplied to obtain another number.
It's called iterated logarithm function. It is a very slowly growing function. For example:
lg*(2) = 1lg*(4) = 2lg*(16) = 3lg*(65536) = 4lg*(2^65536) = 5 /note that (2^65536) is much larger than the number of atoms in the observable universe/Or in the case of Big O it could pretty much be considered as constant time.
168
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
