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
- logarithm — The number of times you must divide a number by a base, usually two in computing, to get down to one.
- binary search — Finding a target in sorted data by comparing it with the middle item and throwing away the half where it cannot be.
- balanced tree — A tree kept close to its minimum possible height, O(log n), so that searches never take long paths.
- growth rate — The rule that says how fast an algorithm's cost rises as the input size n rises, such as constant, linear or quadratic.
- min-heap — A heap in which every parent is less than or equal to its children, so the minimum is at the root; a max-heap reverses the order.
- data structure — A way of arranging data in memory, such as a list, dictionary, tree or graph, so that certain operations become cheap.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Binary Search And Its Invariant — Algorithms & Data Structures for Working Engineers
- Searching With Hashes Versus Trees — Algorithms & Data Structures for Working Engineers
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers
- Timers Phase: setTimeout, Min-Heap Scheduling & Drift — Node.js Internals & Backend Services