Logarithm(log n)

How many times a number can be halved before it reaches one. A million halves about twenty times, so a search that halves the range each step costs about twenty steps at any large size. Halving is where logarithmic cost comes from.

• See also: Computational complexity
• See also: Binary search
• Used in: Measuring Work

Back to the glossary