Binary logarithm

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/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.

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.