O(log n) Complexity Explained | Java Fresher Interview
Fast recall
Quick revision
Core answer
Whether you understand why halving yields log n and can name where it appears
Thinking O(log n) requires sorting always, or confusing it with O(n log n)
Quantify it (1B -> ~30 steps) and note the log base is irrelevant in Big-O
Interview-ready guide
Interview answer
O of log n means the algorithm shrinks the problem by a constant factor, usually half, on every step.
If I keep halving n, the number of steps it takes to get down to one is the base-two logarithm of n. That's what makes it so fast: every time the input doubles, I only need one extra step. To put numbers on it, a million elements is about twenty steps, and a billion is only about thirty.
It shows up anywhere I throw away a fixed fraction of the work each iteration. The classic example is binary search, where each comparison discards half of the remaining range. It also appears in balanced binary search trees like Java's TreeMap and TreeSet, where search, insert, and delete all run in time proportional to the tree's height, which is log n.
And it shows up in heaps, or PriorityQueue, where pushing and popping bubble an element up or down along the height of the tree. One thing I'd clarify is that I don't worry about the base of the logarithm, base two, base ten, natural log, because changing the base only multiplies by a constant factor, and Big-O ignores constants.
Two mistakes I avoid: first, confusing O of log n with O of n log n, which is different, that's doing n operations where each does log n work, like sorting. And second, assuming log n requires a sorted array. Binary search does, but heaps and balanced trees give me log n without the data being sorted.
O(log n) Complexity Explained | Java Fresher Interview
Direct Answer
O(log n) means the work grows by only one step each time the input doubles, because the algorithm halves the problem at every stage. It appears in binary search, balanced BST operations, and heap insert/remove. It's extremely fast: a billion elements take only ~30 steps. The base of the log (2, 10, e) is dropped in Big-O since they differ by a constant factor.
Code Example
// Halving loop: runs log2(n) times
for (int k = n; k >= 1; k /= 2) doWork(); // n=16 -> 16,8,4,2,1 = 5 steps
// Binary search: O(log n) - each step discards half the range
int bsearch(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
else if (a[mid] < target) lo = mid + 1; // drop left half
else hi = mid - 1; // drop right half
}
return -1;
}
// 1,000,000 elements -> about 20 comparisons
Common Mistakes & Pitfalls
- O(log n) needs sorting always: binary search does, but heaps and balanced trees give log n without a sorted array.
- Confusing with O(n log n): log n is one halving sweep; n log n is n operations each doing log n work (e.g. sorting).
- Worrying about log base: base 2 vs 10 only changes a constant factor - dropped in Big-O.
- Assuming log n is slow: it's near-constant in practice for huge n.
Check your understanding
Answer these without looking back at the article.
- What is binary search and when can you use it?
- Why is a balanced BST O(log n) but an unbalanced one O(n)?
- What is the complexity of heap operations?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.