Course contentsShow
← Computer Science
Lesson 286 of 2,8727. Introduction to Complexity AnalysisFree lesson

O(n log n): Linearithmic Time

Examining efficient sorting algorithms like mergesort and quicksort that combine linear and logarithmic factors.

O(n log n): Linearithmic Time

What you'll learn: You'll understand what "linearithmic" complexity means and why the most efficient general-purpose sorting algorithms achieve this performance.

The Core Idea

Linearithmic time combines two growth rates you've already seen: linear (O(n)) and logarithmic (O(log n)). When an algorithm's runtime grows as O(n log n), it means for input size n, the algorithm performs roughly n × log n operations.

This complexity sits between O(n) and O(n²) in terms of speed—faster than quadratic but slower than pure linear.

Why O(n log n) Appears in Sorting

Efficient sorting algorithms like mergesort and quicksort achieve O(n log n) time by cleverly combining:

  1. Divide-and-conquer structure (the log n part): They split the problem into smaller subproblems recursively, creating log n "levels" of division
  2. Linear work at each level (the n part): At every level of recursion, they do O(n) total work processing or merging elements

Think of it like organizing a huge pile of papers: instead of comparing every paper to every other paper (O(n²)), you repeatedly split the pile in half, sort each half, then merge them back together efficiently. The splitting creates log n levels, and merging at each level touches all n items once.

Practical Impact

For 1,000 items:

  • O(n²) ≈ 1,000,000 operations
  • O(n log n) ≈ 10,000 operations (much better!)
  • O(n) ≈ 1,000 operations

This makes O(n log n) algorithms practical for sorting large datasets where O(n²) algorithms would be painfully slow.

Key Takeaway: O(n log n) linearithmic time characterizes efficient divide-and-conquer algorithms like mergesort, combining logarithmic recursion depth with linear work per level—the sweet spot for general-purpose sorting.