Binary logarithm

For thoughtful child sponsors

Logarithms in the form log₂n are called Binary logarithms or Base 2 logarithms. Base 2 logarithms are frequently written lg n.

Algorithms and data structures that are binary in nature, like Binary search trees and binary partition halving, make use of the lg n property. For BSTs, basic dynamic set algorithms can be designed to operate on BSTs in lg n time.

Binary partition halving can split an array in lg n time. As an example, a recursive algorithm can split an array of size n into two n/2 arrays. The algorithm can call itself and split those two n/2 arrays into four n/4 arrays, and so forth. During each iteration i, the size of the input array is n/2ⁱ. Assuming that the algorithm ends at array of size 1 (the base case), 2ⁱ = n. Using the binary logarithm on 2ⁱ, we see that i iterations takes lg n time.

In information theory the definition of the amount of self-information involves a base 2 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.

Also, binary algorithms that are multiplied by a linear term are sometimes called linearithmic (n lg n).

Many algorithms grow in lg n or n lg n time. Some examples include:

average time quicksort
Binary search trees
merge sort
Monge array calculation
... many others.

Compare: natural logarithm (Base e), common logarithm (Base 10)