Why Logarithms are Beautiful?

logarithms

Binary logarithms or log2 n is the power to which the number 2 must be raised to obtain value n. Binary logarithm (and others) has numerous applications in computer science. Let’s take analysis of algorithms for example. All algorithms have a running time, also called time complexity of algorithms.

An algorithm’s running time is measured against size of the input. When an algorithm’s running time increases in exponential proportion to the input size it is exponential time. This can be represented as O (cn) using Big-O notation. But when dealing with algorithms where time complexity decreases with each iteration by a factor of any given number, representation becomes difficult. This is where logarithms help because logx n is inverse of nx.

An Example

Take example of binary search, if we had a sorted list of 32 elements running time can be computed as:

Iteration Running Time
1 32
2 16
3 8
4 4
5 2

At each iteration running time decreases by a factor of 2. Thus we say that time complexity of binary search algorithm is O (log2 n). If there is a function whose running time decreases by a factor of 5 it can be represented as O (log5 n). Generally it is written as O (lg n). Without logarithms it would have been really ugly to represent slowly growing functions.

References

  1. Binary logarithms, Wikipedia
  2. Logarithmic growth, Wikipedia
  3. BigOCheatSheet.com
  4. Working with exponentials and logarithms, MathIsFun.com

Comments

avatar
  Subscribe  
Notify of