Logarithmic Time and Space Olog n

Logarithmic Time and Space O(log n)

Imagine a phone book with a million names. You never read it page by page. You flip to the middle, decide whether your name is before or after, and instantly throw away half the book. Then you do it again on what remains, and again. After a surprisingly small number of flips you are holding a single page. That "throw away half every step" behaviour is the soul of logarithmic time: the input can be enormous, yet the work grows only as fast as how many times you can halve it.

The key intuition: an algorithm is O(log n) when each step shrinks the problem by a constant factor (÷2, ÷3, ÷10 — the base doesn't matter), rather than by a constant amount (−1). Cutting a fixed slice off makes it linear; cutting a fixed fraction makes it logarithmic. That difference is why log n is one of the most prized shapes in all of computer science.

Precise definition

A function T(n) is O(log n) if there exist constants c > 0 and n0 such that T(n) ≤ c · log n for all n ≥ n0. It is an upper bound: the running time grows no faster than the logarithm of the input size, ignoring constant factors.

Why the base is irrelevant in Big-O: changing logarithm base only multiplies by a constant, since log2n = log10n / log102. Big-O absorbs that constant, so O(log2n) = O(log10n) = O(ln n) = O(log n). We write plain log n. (In CS the implied base is 2, because we usually halve.)

The defining property: to reach a single element from n by repeated halving, you need k steps where n / 2k = 1, i.e. 2k = n, i.e. k = log2n. Logarithm is the inverse of exponentiation — it answers "how many times do I multiply by 2 to reach n?"

Worked example: binary search, operations counted

Search for the value 23 in a sorted array of 16 elements: indices 0–15 holding [2, 5, 8, 12, 16, 19, 23, 27, 31, 38, 41, 45, 50, 58, 63, 70]. We track a window [lo, hi] and probe its midpoint.

• Step 1: lo=0, hi=15, mid=7 → arr[7]=27. 23 < 27, so discard the right half. hi=6. (16 → 7 live candidates)
• Step 2: lo=0, hi=6, mid=3 → arr[3]=12. 23 > 12, discard left half. lo=4. (7 → 3 live candidates)
• Step 3: lo=4, hi=6, mid=5 → arr[5]=19. 23 > 19, discard left. lo=6. (3 → 1 live candidate)
• Step 4: lo=6, hi=6, mid=6 → arr[6]=23. Found. (probe the last candidate)

Four comparisons for 16 elements — and log216 = 4. Each probe removes the midpoint plus an entire half, so the live window shrinks 16 → 7 → 3 → 1 — at most ⌈(k-1)/2⌉ of k candidates ever survive a probe, which is what caps the comparisons at ⌈log2(n+1)⌉. That is the whole point: double the array to 32 and you need just one more comparison, not twice as many. A billion elements? About 30 comparisons. Contrast a linear scan, which would take up to 16 comparisons here and a billion there.

Best case is O(1): the middle element is the target on the first probe. Worst and average case are both O(log n) — the average is log2n − 1 comparisons, only a hair below the worst. There is no bad input that degrades binary search to linear (unlike, say, quicksort).

Pitfalls and what an interviewer probes

• "Where's the log coming from?" Interviewers want you to name the halving. If you can't point to a step that discards a constant fraction of the remaining work, it probably isn't O(log n). Repeated ÷2, balanced-tree descent, or exponent-style jumps are the tells.
• Log inside a loop. A loop that runs n times and does an O(log n) operation each pass (e.g. n inserts into a balanced BST or heap) is O(n log n), not O(log n). Watch the nesting.
• Prerequisites hide the real cost. Binary search is O(log n) only on already-sorted data. If you sort first, the honest total is O(n log n) + O(log n) = O(n log n). One-off search on unsorted data? A linear O(n) scan beats sort-then-search.
• Unbalanced structures. A binary search tree gives O(log n) lookup only when balanced. Insert sorted data into a naive BST and it degrades to a linked list — O(n) worst case. This is why we use AVL / red-black trees.
• Space vs time. Iterative binary search is O(1) auxiliary space. The recursive version uses O(log n) space for the call stack — one frame per halving. "Logarithmic space" most often means recursion/stack depth, as in the log-depth recursion of balanced divide-and-conquer.

When it matters + trade-offs vs neighbours

Logarithmic growth is essentially "free" at scale — the reason databases and filesystems lean on it everywhere. A B-tree index turns a lookup over billions of rows into a handful of disk reads (log base = the branching factor, often hundreds, so the tree is very shallow). Balanced BSTs, heaps (O(log n) push/pop), and skip lists all trade a little structural bookkeeping for logarithmic operations.

Place it on the ladder to feel the value:

• O(1) — constant. Better, but hash tables buy it with memory overhead and lose sorted-order traversal that a tree keeps.
• O(log n) — this. For n = 1,000,000, about 20 steps.
• O(n) — linear. Same n = 1,000,000 steps. The gap (20 vs a million) is why halving is so powerful.
• O(n log n) — the practical floor for comparison sorting; log n is the multiplicative "tax" on a linear pass.

The trade-off to state honestly: log n structures usually require the data to be ordered or balanced, which costs on insertion and adds implementation complexity. For tiny n, a simple O(n) scan is often faster in wall-clock time because it has better cache locality and no constant-factor overhead. Log n wins decisively as n grows large — which is exactly when it counts.

Key takeaways

• Constant fraction, not constant amount: O(log n) arises when each step discards a fixed proportion of the remaining work (÷2), so cost = number of halvings = log2n.
• Doubling the input adds one step, not double the work — a billion items take ~30 comparisons. The Big-O base is irrelevant (it's just a constant factor).
• Prerequisites and balance are load-bearing: binary search needs sorted input; trees need balancing, or the bound silently degrades to O(n).
• Time vs space: iterative log-n algorithms are O(1) space; recursive divide-and-conquer costs O(log n) stack depth. Beware a log-n op inside an n-loop — that's O(n log n).