logarithmic time

Work that grows by only one step each time the input doubles, written O(log n), typical of algorithms that halve the problem each step.

In more detail

Binary search and walking down a balanced tree are logarithmic: each step throws away half of what is left. Doubling a million items to two million adds just one more step. That is why a sorted list or a balanced tree can search a billion items in about thirty comparisons.

Related terms

Taught in

References