Back to Catalog
Big O
Efficient
O(log n) - Logarithmic Time
Cuts the problem in half each step — searching a billion items in ~30 steps.
Intent & Description
Real-world Use Case
Git bisect — finding which commit introduced a bug in a repo of 1,024 commits takes only 10 binary search steps. Database B-tree index lookup — finding a row in a 100M row table takes ~27 B-tree node reads. Both are textbook O(log n).
Source
📌 TL;DR
O(log n) = halving the problem every step. 30 steps on a billion items. Essential for search, trees, and heaps. Requires sorted/structured data.
Advantages
- Handles enormous datasets with minimal steps — 1B items in ~30 steps
- Standard in databases (B-tree indexes), language runtimes (TreeMap), and system libraries
- Far better than O(n) for large sorted datasets
- Stack depth for recursive divide-and-conquer is only O(log n) deep
Disadvantages
- Data usually needs to be sorted first — sorting is at least O(n log n)
- Tree structures need balancing to guarantee O(log n) — unbalanced trees degrade to O(n)
- More complex to implement than linear scan
- Overhead from pointer chasing in tree structures — worse cache locality than array scan for small n
Implementation Example
// O(log n) — Binary Search (iterative, avoids stack overhead)
function binarySearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = (lo + hi) >>> 1; // Bitwise right shift — no overflow risk
if (arr[mid] === target) return mid;
arr[mid] < target ? lo = mid + 1 : hi = mid - 1;
// Each iteration halves the search space — O(log n) total
}
return -1;
}
// O(log n) — Fast exponentiation (square instead of multiply n times)
function fastPow(base, exp) {
if (exp === 0) return 1;
if (exp % 2 === 0) {
const half = fastPow(base, exp / 2); // Recurse on half — O(log n) depth
return half * half;
}
return base * fastPow(base, exp - 1);
}
// Demo: binary search on 1 billion items takes ~30 iterations
// Math.ceil(Math.log2(1_000_000_000)) === 30