Lesson 9

In discrete mathematics, the logarithmic function appears most frequently with base two. Also, in most cases, when the base of the logarithm is omitted, it is the binary logarithm that is used implicitly. Here are some natural appearances of \(\log_{2} n\).

• The number of bits in a binary representation of \(n\) is about \(\log_{2} n\).


• The number of times you need to halve \(n\) to get \(1\) is about \(\log_{2} n\). Perhaps the most well known application of this is estimating the running time of the binary search algorithm.


• The depth of a complete binary tree with \(n\) leaves is about \(\log_{2} n\).