Binary logarithm
Logarithms in the form log2n 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 2 n/2 arrays. The algorithm can call itself and split those 2 n/2 arrays into 4 n/4 arrays, and so forth. During each iteration i, the size of the input array is n/2i. Assuming that the algorithm ends at array of size 1 (the base case), 2i = n. Using the binary logarithm on 2i, we see that i iterations takes lg n time.
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)
