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.0math.ceil(math.log2(1_000_000)) == 20Related terms
- 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.
- binary search — Finding a target in sorted data by comparing it with the middle item and throwing away the half where it cannot be.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Bloom Filters: Membership Without The Data — Algorithms & Data Structures for Working Engineers
- Deques And Ring Buffers — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers