O(log n) vs O(n log n): what the difference actually means

At a billion elements, an O(log n) algorithm does about 30 steps and an O(n log n) algorithm does about 30 billion. They differ by a factor of n, which is the entire input. The difference comes down to one question: does the algorithm have to touch every element, or can it throw most of them away unexamined?

The two notations look similar on the page, and that similarity is exactly why they get swapped in interviews and in code review. But they describe opposite strategies. One is the cost of finding something. The other is the cost of organising everything. Confusing them is not a maths error. It is a missing question about what your loop is doing.

What is the difference between O(log n) and O(n log n)?

O(log n) means the work shrinks the problem by a constant factor each step and never visits most of the input. O(n log n) means every one of the n elements is processed, and each one carries a log-sized cost. The multiplication by n is the tell: it says "for all of them," which is precisely what a logarithmic algorithm refuses to do.

A useful test is to ask what your algorithm would do if I deleted a random element from the input without telling it. A binary search would usually never notice, because it only ever reads about 30 of a billion positions. A merge sort would produce a different output, because it read every position. Algorithms that can be correct while ignoring most of their input are the logarithmic family. Algorithms that must observe everything have an n in front, and the only question left is what each observation costs.

Picture a parcel sorting facility. Looking up one address in the sorted directory on the wall is the logarithmic operation: you open the book near the middle, decide which half the street name is in, and repeat. Most pages are never opened. Now consider sorting the day's intake instead. Every parcel must physically pass through the building, and it goes through a sequence of splitting stages, one bin becoming two, until each parcel is alone in its own destination bin. Every parcel travels through every stage. The number of stages is how many times you can halve the pile, and the work per stage is one pass over all the parcels. Stages times parcels is where n log n comes from, and there is no way to skip a parcel, because an unsorted parcel is a wrong answer.

Why is binary search O(log n)?

Because the surviving range halves on every comparison, and you can only halve a number of size n a limited number of times before reaching 1.

def binary_search(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1      # discard the left half
        else:
            hi = mid - 1      # discard the right half
    return -1

Here is the counting argument, which matters far more than the code. Let k be the number of iterations. The range starts at size n, and each iteration replaces it with at most half of itself, so after k iterations the range has size at most n divided by 2^k. The loop stops when the range is empty, which happens once n over 2^k drops below 1, that is once 2^k exceeds n. Solving for k gives k greater than log₂(n). So the loop runs at most log₂(n) plus one times, and each iteration does a fixed amount of work: one midpoint calculation, one array read, one comparison. Constant work repeated log n times is O(log n). Notice what never appears in that argument: the size of the array in memory, the cost of reading elements you skipped, any pass over the data. The algorithm reads at most 30 of a billion elements and is provably correct anyway, which is only possible because sortedness lets it prove that the discarded half cannot contain the target. Take away the sorted precondition and the whole argument collapses, since discarding becomes unjustified and you are back to scanning everything at O(n). That precondition is doing all the work, a point developed further in complexity is a contract, not a fact.

Why is merge sort O(n log n)?

Because it has log n levels of recursion, and every level does a full pass over all n elements.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)     # one linear pass over both halves

def merge(x, y):
    out, i, j = [], 0, 0
    while i < len(x) and j < len(y):
        if x[i] <= y[j]:
            out.append(x[i]); i += 1
        else:
            out.append(y[j]); j += 1
    return out + x[i:] + y[j:]

Count it by levels rather than by calls, which is the trick that makes this tractable. At the top level there is one problem of size n. Below it, two problems of size n over 2. Below that, four of size n over 4, and so on. At every level the subproblem sizes sum to exactly n, because the split is a partition and nothing is duplicated or lost. The merge step at each level is linear in the number of elements it handles, so the total work on any single level is proportional to n. Now count the levels: sizes go n, n over 2, n over 4, and halving stops at 1, which is the same halving count as before, so there are about log₂(n) levels. Multiply n work per level by log₂(n) levels and you get n log n. The log factor here means something completely different from the log in binary search: there it counted how many elements survived, here it counts how many times the whole input gets reprocessed. Same symbol, opposite role. This is also why comparison sorts cannot do better than n log n in the worst case, since distinguishing n factorial possible orderings needs at least log₂(n!) comparisons, which is proportional to n log n. The Sorting module works through that lower bound properly.

How do the growth rates compare at real input sizes?

Numbers settle this faster than notation does. Step counts below are rounded, using log₂.

Read the log n column again. It grows by 10 while n grows by a factor of a million. That flatness is why logarithmic algorithms feel like they are not running at all, and why an accidental n in front of a log is one of the most expensive typos in performance work.

How can you tell which one you wrote?

Look at the loop structure and ask whether the input is being discarded or traversed. Three shapes cover nearly every case.

A single loop that halves something is O(log n). If the loop variable is repeatedly divided or multiplied by a constant, and there is no enclosing loop over the elements, you have logarithmic time. Binary search, exponentiation by squaring, and descending a balanced tree all look like this.

A loop over all n elements that does log-sized work inside is O(n log n). This is the shape people most often misread. Pushing each of n elements into a heap is n pushes at O(log n) each. Inserting n keys into a balanced tree is the same arithmetic. Doing a binary search inside a loop over every element is too. The giveaway is a for over the data wrapping something logarithmic, and the multiplication is literal: n iterations times log n per iteration.

Sorting anywhere in the function makes the function at least O(n log n). A comparison sort dominates any linear work around it, so a function that sorts and then does a single pass is n log n, not n. This is worth internalising because it flips the answer to a lot of interview questions. The two-pointer solution to 3sum is often described as O(n²), and the sort is genuinely free there only because n² already dominates n log n.

The expensive mistake is sorting inside a loop. A sort nested in a pass over n elements is n times n log n, which is n² log n, worse than the naive nested loop you were probably trying to improve on. When you see a sort inside a loop, the fix is usually to sort once outside it, or to maintain a heap instead so that each update costs log n rather than a full re-sort. That heap technique is the basis of top-K frequent elements, and the underlying structure is covered in the heap as an array.

Does the difference matter in practice, or only in interviews?

It matters most at the boundary where one of them stops fitting in your latency budget. Below roughly ten thousand elements, the constant factors and memory behaviour often matter more than the exponent, and a well-laid-out O(n log n) routine can beat a pointer-chasing O(log n) structure that thrashes the cache. I have measured that outcome more than once, and it is the argument in why arrays beat linked lists in practice.

Above that, the asymptotics take over and nothing rescues the wrong class. If you are searching a billion-row index on every request, the difference between 30 steps and 30 billion is the difference between a database and an outage. The practical instinct worth building is not "always pick the smaller exponent" but "know which side of the boundary you are on, and know what precondition buys you the smaller one." Logarithmic time is almost never free: it is purchased with sortedness, with a tree or heap you had to build, or with an index you had to maintain. Someone paid n log n earlier so that you could pay log n now.

If you want to make this concrete, work search in rotated sorted array next and state the halving argument out loud before you write any code, then read binary search on the answer, which is where the logarithmic idea stops being about arrays and starts being about search spaces.

Frequently asked questions

Is O(n log n) closer to O(n) or to O(n²)?

Much closer to O(n). At a million elements, n log n is about 20 times n, while n² is a million times n. Because log n grows so slowly, n log n behaves like a slightly expensive linear algorithm across every input size you are likely to meet. Treating it as "linear with a small tax" is a reasonable working intuition; treating it as "nearly quadratic" is not.

Does the base of the logarithm matter?

Not for the big-O class, because changing base multiplies by a constant, and constants are dropped. log₂(n) and log₁₀(n) differ by a factor of about 3.3. It does matter for reasoning about real step counts, which is why base 2 is the convention in algorithm analysis: it corresponds to halving, which is what the algorithms actually do.

Can sorting ever be faster than O(n log n)?

Yes, if you stop comparing elements. The n log n lower bound applies only to comparison-based sorts. Counting sort and radix sort exploit the structure of the keys instead, sorting integers in a bounded range in O(n + k) or O(dn) time. The trade is generality and memory, and the details are in counting and radix sort.