Logarithmic Time
Runtime that grows logarithmically with input size.
Formula
Variables
Example
Binary search
How it works
O(log n) means the work needed increases very slowly as the input gets bigger, because each step removes or narrows down a constant fraction of the remaining possibilities. This usually happens when an algorithm repeatedly halves the problem, such as by discarding one branch of a search space or reducing a data structure in stages. The base of the logarithm does not matter in Big-O notation, because changing the base only multiplies the result by a constant factor.
When to use it
Use this for algorithms that repeatedly split a problem into smaller parts or eliminate large chunks of data at each step, such as operations on balanced trees, heaps, or divide-and-conquer searches. It is especially relevant when the number of remaining candidates shrinks by a fixed ratio rather than by a fixed amount.
Worked example, step by step
Suppose an algorithm halves the remaining problem size each step, starting from n = 1,024. Step 1: 1,024 → 512 Step 2: 512 → 256 Step 3: 256 → 128 Step 4: 128 → 64 Step 5: 64 → 32 Step 6: 32 → 16 Step 7: 16 → 8 Step 8: 8 → 4 Step 9: 4 → 2 Step 10: 2 → 1 The number of steps is 10, so the runtime grows like log2(1,024) = 10. If n doubled to 2,048, the steps would increase to 11, not 20, showing logarithmic growth.
Common mistakes to avoid
- Thinking O(log n) means the runtime is constant because the increase is small
- Assuming the logarithm base changes the Big-O class
- Confusing logarithmic growth with linear growth after repeated halving
Did You Know?
Logarithmic time means a billion items take only about 30 steps, the magic behind binary search.
Share this formula
More in Computer Science
View allShannon Entropy
AdvancedAverage information content of a random source (bits).
Master Theorem (form)
AdvancedAnalyzes running time of divide-and-conquer algorithms.
Hamming Distance
AdvancedNumber of positions at which two strings differ.
Bits to Represent n
BasicMinimum number of bits to represent n distinct values.
Binary to Decimal
BasicConverts a binary number to decimal.
Nodes in a Full Binary Tree
IntermediateTotal nodes in a perfect binary tree of height h.