log₂n

The number of times it takes to divide n in half until you can't divide it anymore is log2n. This log comes up very often in the analysis of algorithms that continuously divide something in half.

Mathematical Explanation

We can express the division of n in half x times to get 1 using the following equation:

n / 2x = 1

Solving the equation for x we get:

  • n / 2x = 1
  • n = 2x
  • logn = log2x
  • logn = xlog2
  • logn / log2 = x
  • x = log2n

Example:

An example of something that has a runtime of O (logn) is binary-search, which searches an array by constantly dividing the array in half until it finds the number it is searching for.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License