Linearithmic Time On log n

Linearithmic Time: O(n log n)

Imagine you have to sort a shuffled deck of n cards. You could compare every card against every other card, but that is wasteful. A smarter idea: split the pile in half, sort each half, then merge the two sorted halves together. Splitting keeps halving the problem until each piece is trivially sorted, and merging stitches them back. The halving gives you a log n factor (how many times you can cut n in half before reaching 1), and each round of merging still has to touch all n items once. Multiply those two forces together and you get n × log n work. That product is what we call linearithmic time.

The mental picture: it is almost as cheap as looking at each item once (linear, O(n)), but with a small, slowly-growing multiplier bolted on. For a million items, log₂(n) ≈ 20 — so linearithmic is only about 20× more work than linear, not a million times more. That is why it feels “fast enough” in practice.

Precise definition

An algorithm runs in linearithmic time when its running time T(n) grows proportionally to n · log n — formally, T(n) = O(n log n). In big-O, the logarithm's base is irrelevant: log₂ n, log₁₀ n, and ln n differ only by a constant factor, which big-O absorbs. By convention we read it as base 2 because the recurring pattern is repeated halving.

The canonical way this arises is a divide-and-conquer recurrence:

• T(n) = 2·T(n/2) + O(n)

Read it as: split into two halves, solve each (2·T(n/2)), then do linear O(n) work to combine. By the Master Theorem this solves to T(n) = O(n log n). The two ingredients you must always be able to point to are: (1) a log n number of levels from repeated division, and (2) O(n) work spread across each level.

Worked example: merge sort on 8 elements

Take n = 8 and count the real comparisons/moves. Merge sort recursively halves the array, so the number of levels is log₂ 8 = 3 (8 → 4 → 2 → 1). At every level, the total merging work touches all 8 elements exactly once — because the sub-arrays at a level partition the whole array.

• Level 1 (merge pairs of size 4 into size 8): ~8 element moves.
• Level 2 (merge four pieces of size 2 into fours): ~8 element moves total.
• Level 3 (merge eight singletons into pairs): ~8 element moves total.

Total ≈ 8 × 3 = 24 operations = n × log₂ n. Contrast the neighbours: a linear scan would be 8, and a quadratic O(n²) algorithm like bubble sort would be 8² = 64. For n = 1,000,000 the gap explodes: linearithmic ≈ 20,000,000 ops, quadratic ≈ 1,000,000,000,000 — a 50,000× difference. That is the entire reason we prefer O(n log n) sorts at scale.

Best / worst / average: merge sort is O(n log n) in all three cases — the halving structure is fixed regardless of input order. Quicksort is O(n log n) on average but degrades to O(n²) worst-case (bad pivots); heapsort is O(n log n) worst-case too. Comparison-based sorting cannot beat O(n log n) in the worst case — that is a proven lower bound.

Common pitfalls & what an interviewer probes

• Confusing O(n log n) with O(log n). A log-time algorithm does work at only one position per level (like binary search discarding half). Linearithmic does O(n) work per level. The n multiplier is the whole difference.
• Assuming every nested loop is O(n²). An interviewer will show a loop whose inner bound shrinks or doubles — e.g. for i in 1..n: for j = 1; j < n; j *= 2. The inner loop runs log n times, so total is O(n log n), not O(n²). Watch how the inner counter changes.
• Forgetting the “combine” cost. The recurrence is only linearithmic when the merge/partition step is O(n). If combining were O(n²), T(n)=2T(n/2)+O(n²) solves to O(n²) instead.
• Space. Interviewers pair time with space: merge sort needs O(n) auxiliary space; heapsort sorts in O(1) extra space. Same time class, different memory trade-off.
• “Can you do better?” For comparison sorts, no — and you should be able to prove it: a comparison sort is a decision tree with one leaf per possible ordering, so it has n! leaves; a binary tree with n! leaves has height at least log₂(n!) = Ω(n log n) (by Stirling's approximation, log₂(n!) ≈ n log₂ n). That height is the worst-case comparison count, hence the Ω(n log n) lower bound. But if you can exploit structure (integer keys, bounded range), counting/radix sort escape the comparison model and hit O(n) — a classic follow-up they want you to reach for.

When it matters in practice + trade-offs

Linearithmic time is the sweet spot for problems that provably cannot be linear. It shows up in: all efficient comparison sorts (merge, heap, introsort — the basis of most standard library sort() functions), building a balanced binary search tree by inserting n items, many divide-and-conquer results (closest pair of points, FFT), and the ubiquitous “sort first, then scan” pattern that turns an O(n²) brute force into O(n log n) — e.g. detecting duplicates, interval merging, or two-sum on a sorted array.

Trade-off framing versus neighbours: O(n) is strictly cheaper but often unattainable when ordering or global structure is required. O(n²) is simpler to code and can win for tiny n (constants matter — real sorts switch to insertion sort below ~16 elements). The practical rule: once n reaches the thousands, an O(n log n) solution dominates a quadratic one so decisively that finding one is usually the intended interview answer.

Key takeaways

• O(n log n) = linear work repeated across log n levels of halving; recognise it from the recurrence T(n) = 2T(n/2) + O(n).
• The log factor grows glacially (~20 for a million), so linearithmic is only a small multiple of linear — and vastly better than quadratic at scale.
• It is the proven lower bound for comparison-based sorting; merge/heapsort hit it in the worst case, quicksort on average.
• Interview reflex: if a brute force is O(n²), ask whether sorting first or divide-and-conquer drops it to O(n log n).