Main Page | See live article | Alphabetical index 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) This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.