What Is Logarithmic Time Complexity? O(log n) Explained
- Logarithmic time complexity (O(log n)) means each step discards a constant fraction of remaining work, so doubling the input adds exactly one more step.
- Binary search is the clearest example: each comparison eliminates half the array, giving at most log₂ n steps for n elements.
- Balanced trees and heaps achieve O(log n) operations by keeping height at O(log n), not O(n), by construction.
- O(log n) vs O(n log n): if one path is followed and the rest discarded, you get O(log n); if every element is touched at every level, you get O(n log n).
- Binary search on the answer is the interview pattern that trips people: search over possible output values when you can check any candidate in O(n) time.
- Iterative binary search is O(1) space; recursive binary search carries O(log n) stack depth, which compounds on unbalanced trees.
- When you claim O(log n) in an interview, name what's being halved—that single habit transfers to every variant you've never seen.
You've been writing code for a while. You know what O(n) means: the loop runs once per element. You know O(n²) means nested loops and regret. Then you see O(log n) in someone's analysis and you nod along, hoping it becomes clear from context.
It does not become clear from context.
An algorithm has logarithmic time complexity, O(log n), if on each step it discards a constant fraction of the remaining work. With a million elements, that's roughly 20 steps. With a billion, it's 30. Doubling the input adds exactly one more step. That property comes from one thing: halving.
Halving Is the Whole Definition
Usually that fraction is half. Every time you cut the problem in half, you get log₂ n steps before nothing is left. With 1,000 elements, that's about 10 steps.
That's it. The rest is just noticing when halving is happening. Everything else is commentary.
What "Logarithm" Actually Means
If 2^10 = 1,024, then log₂(1,024) = 10. The logarithm answers a surprisingly useful question: how many times can I cut this number in half before I hit 1?
1,024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1
That's 10 halvings. So log₂(1,024) = 10.
The practical upshot: doubling n only adds one more step. Go from a million elements to two million, and your algorithm does one more operation. Go from a million to a trillion and you've added about 20.
| n | log₂(n) |
|---|---|
| 8 | 3 |
| 64 | 6 |
| 1,024 | 10 |
| 1,000,000 | ~20 |
| 1,000,000,000 | ~30 |
In Big-O notation, we drop the base because changing it just multiplies by a constant, and Big-O ignores constants. O(log₂ n) and O(log₁₀ n) are the same complexity class. You'll always see it written as O(log n). No base. The base doesn't matter. Math teachers hate this one trick.
Binary Search Makes the Halving Concrete
Binary search on a sorted array is the clearest illustration. (The binary search invariant is what lets you confidently throw away the wrong half every iteration.)
The problem: find the index of a target value in a sorted array. The naive approach is a linear scan. O(n). Check every element until you find it or run out. Fine, works, nobody is impressed.
Binary search exploits the sorted order instead.
def binary_search(nums: list[int], target: int) -> int: left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1
Each iteration compares the middle element to the target. If they don't match, half the array is provably irrelevant. You throw it away. No grief. No second-guessing.
Start with n elements. After one step: n/2. After two: n/4. After k steps: n/2^k. The loop ends when n/2^k = 1, which happens when k = log₂ n.
The reason it's O(log n) isn't the comparison. It's that each comparison eliminates half the search space.
When you realize production has been doing an O(n) scan on a sorted million-item array for six months.
The Halving Pattern Is Everywhere
Once you see it in binary search, you see it everywhere. This is either exciting or mildly annoying, depending on your mood.
Balanced binary search trees (AVL trees, red-black trees) maintain a height of O(log n) by keeping both subtrees balanced. A search or insert traverses at most one path from root to leaf. That path is log n nodes long. The balancing isn't free, but it's why the trees exist.
Heaps have the same structure. When you push an element and bubble it up, or pop the root and bubble down, you traverse at most O(log n) levels. Priority queues are built on this. So is Dijkstra.
Merge sort divides the array in half at every recursion level. The recursion tree has O(log n) levels. Each level does O(n) work to merge, giving the familiar O(n log n) total. The halving is how the recursion terminates; the merging is where all the actual work happens.
Exponentiation by squaring computes x^n in O(log n) multiplications instead of O(n) by halving the exponent on each step: x^n = (x^(n/2))^2. If n is odd: x^n = x × (x^((n-1)/2))^2. The recursion bottoms out in log n levels.
The common thread: there's a structure (a sorted sequence, a balanced tree, a numeric range) that lets you discard half the remaining possibilities with one comparison. Find the structure. The complexity follows.
O(log n) Time Doesn't Mean O(log n) Space
This trips people in interviews more than it should.
Iterative binary search uses O(1) space. The array stays where it is. You move two pointers around. No stack frames, no extra memory. Constant space.
Recursive implementations use O(log n) space because the call stack holds one frame per recursion level, and there are O(log n) levels before the base case hits.
def binary_search_recursive(nums: list[int], target: int, left: int, right: int) -> int: if left > right: return -1 mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: return binary_search_recursive(nums, target, mid + 1, right) else: return binary_search_recursive(nums, target, left, mid - 1)
Same time complexity. Different space. The recursive version is cleaner to read. The iterative version is what you should use if someone says "solve it in constant space." Know both. Know why they differ.
Tree traversals are the most common place this distinction matters. A recursive DFS on a balanced binary tree is O(h) space where h is the height: O(log n) for a balanced tree, O(n) for a degenerate (linear) one. That degenerate case is a sorted linked list wearing a tree costume. Don't let it fool you.
When Logarithmic Time Complexity Should Trigger in Your Head
In an interview, the goal is to recognize before you code that a logarithmic solution exists. You're not hunting for binary search. You're hunting for a search space that can be halved.
The input is sorted (or can be sorted cheaply). A sorted array is a compressed search space. Binary search should be your first instinct for any "find X in sorted array" problem. Unsorted and you only need one query? Not worth the O(n log n) sort cost. Multiple queries? Sort once and binary search every time.
You're looking for a threshold or boundary. "First index where condition X becomes true" and "smallest value that satisfies constraint Y" are binary search problems wearing disguises. The condition partitions the space into a false-region and a true-region. Binary search finds the boundary in O(log n).
The problem involves a balanced tree or heap. These data structures are designed so that operations stay O(log n) by construction. You get the complexity for free. Don't overthink it.
The answer space itself can be halved. This is the one that trips people. Some problems don't binary search the input array at all. They binary search the answer. If the question is "what's the minimum capacity X such that this works?" and you can check any candidate X in O(n) time, you can binary search over X values from 1 to max, paying O(n log max) total. This pattern, binary search on the answer, shows up constantly in medium and hard interview problems. You'll miss it if you're only watching for sorted arrays.
Why O(log n) Matters at the Interview Bar
Interviewers aren't just checking whether you get the right answer. They're checking whether you understand why it works. An O(log n) claim needs justification, not assertion. This is where a lot of people get caught.
The wrong answer: "Binary search is O(log n) because it's fast."
The right answer: "Each iteration eliminates half the remaining elements. Starting from n, we need at most log₂ n iterations before the search space is empty."
One of these is a vibe. One of these is an argument. Interviewers write down which one you gave.
When the follow-up is "prove it" and you've only memorized that binary search is O(log n).
If you can't explain the halving argument, you can't handle the variants. Interviewers will ask about duplicates, rotated arrays, searching on 2D matrices, partial sorting. Your answer is always the same: identify what's being halved and why. Once you can do that, every variant becomes the same problem with different packaging.
O(log n) vs O(n log n): Not the Same
These two get confused more than they should. The difference is whether the halving is the whole algorithm or just one stage of it.
O(log n): binary search, BST lookup, heap push/pop. Work done per step is O(1). There are O(log n) steps. Done.
O(n log n): merge sort, heap sort, building a balanced BST from n elements. There are O(log n) levels, but each level does O(n) total work across all elements.
If every element is touched on every level of your recursive breakdown, you're probably O(n log n). If only one path is followed and the rest discarded, you're probably O(log n).
The clearest test: in binary search, you follow one branch at each level and throw the other half away. In merge sort, every element shows up on every level (spread across different merge calls). That difference is the difference between 20 steps and 20 million steps on a million-element input.
Name the Search Space Before You Write a Line
The hardest part of logarithmic-time problems isn't writing binary search. It's recognizing what you're actually searching over.
Most people practice binary search on explicit sorted arrays. Interviews test binary search on the answer space, on time, on capacity, on rotated arrays. The code is identical each time. The insight that makes each problem click is identifying the quantity being halved.
Practice this deliberately. For every medium binary search problem, name the search space before writing anything. "I'm searching over possible values from 1 to max." "I'm searching for the leftmost index where the condition flips." Say it out loud. That habit transfers to problems you've never seen before.
SpaceComplexity runs voice-based mock interviews where you have to articulate this reasoning out loud, to an AI that pushes back. Saying "I'm binary searching over the answer space because the condition is monotone" to an interviewer is a different skill from writing it in a comment. Practicing that articulation is what closes the gap between knowing the pattern and getting the hire.