logarithm

The number of times you must divide a number by a base, usually two in computing, to get down to one.

In more detail

The base-two logarithm of 1,024 is 10, because halving 1,024 ten times reaches 1. This is why algorithms that halve the problem each step cost O(log n). The natural logarithm uses the base e (about 2.718) and appears in formulas such as the best number of hash functions for a Bloom filter.

Examples

math.log2(1024) == 10.0
math.ceil(math.log2(1_000_000)) == 20

Related terms

Taught in

References