Encyclopedia > Binary logarithm

  Article Content

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:

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

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Fibre optic gyroscope

... Contents Fibre optic gyroscope wikipedia.org dumped 2003-03-17 with ...

This page was created in 53.5 ms