log₂n

The number of times it takes to divide `n` in half until you can't divide it anymore is `log _{2}n`. 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 / 2 ^{x} = 1`

Solving the equation for `x` we get:

`n / 2`^{x}= 1`n = 2`^{x}`logn = log2`^{x}`logn = xlog2``logn / log2 = x``x = log`_{2}n

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