Binary logarithm
|
|
In mathematics, binary logarithm is the logarithm in the base 2 (log2n). Binary logarithm is frequently written lg n. It is the inverse function of the exponential function 2n.
Binary logarithm is often used in computer science and information theory, because it is closely connected to the binary numeral system. The number of digits (bits) in the binary representation of a positive integer number n is the integral part of lg n + 1, i.e.
- <math> \lfloor \lg n\rfloor + 1.<math>
In information theory, the definition of the amount of self-information and information entropy involves binary logarithm; this is needed because the unit of information, the bit, refers to information resulting from an occurrence of one of two equally probable alternatives.
Binary logarithm also frequently appears in the analysis of algorithms. If we start with number n greater than 1, and repeatedly divide it by 2, the number of iterations needed to get a value at most 1 is again the integral part of lg n. This idea is used in the analysis of several algorithms and data structures. For example in binary search, the size of the problem to be solved is halved in each iterations, therefore roughly lg n iterations are needed to obtain a problem of size 1, which is solved easily in constant time. Similarly, a perfectly balanced binary search tree containing n elements has height lg n+1.
However, the running time of an algorithm is usually expressed in big O notation, ignoring constant factors. Since log2 n = (1/logk 2)logk n, where k can be any number greater than 1, algorithms that run in O(log2 n) time also run in, say, O(log13 n) time. Base of a logarithm in expressions O(log n) or O(n log n) is thus not important. In other contexts, though, base of a logarithm needs to be specified. For example O(2lg n) is not the same as O(2ln n) because the former is equal to O(n) and later to O(n0.6931...).
Algorithms with running time n lg n are sometimes called linearithmic. Some examples with running time O(lg n) or O(n lg n) include:
- average time quicksort
- binary search trees
- merge sort
- Monge array calculation
- ... many others.
Compare: natural logarithm (Base e), common logarithm (Base 10)pl:Logarytm binarny