n log n time

Between plain linear time, Theta(n), and quadratic time, Theta(n^2), sits a hugely important middle rung: Theta(n log n), pronounced 'n log n' and often called linearithmic. It is the running time of the best general-purpose sorting algorithms and of countless divide-and-conquer methods, so it is worth understanding as its own landmark rather than a footnote.

The function n log n is only a touch above linear, because the logarithm grows so slowly: for n = 1,000,000, log2(n) is about 20, so n log n is about 20 million — only twenty times the linear cost of a million, not a million times. That is why an n log n algorithm feels almost as fast as a linear one in practice and dramatically faster than a quadratic one. The shape arises naturally from divide-and-conquer: if you split a problem of size n into halves, recurse, and spend linear time merging, you get the recurrence whose solution is Theta(n log n) — there are about log2(n) levels of halving, and each level does Theta(n) total work, so the product is n log n. Merge sort is the textbook instance.

n log n matters because it is, for many problems, the best you can do: comparison-based sorting has a proven Omega(n log n) lower bound, so merge sort and heapsort are asymptotically optimal in that model — you cannot beat n log n by being clever, only by changing the model (for example counting sort on small integers). When you see n log n, mentally file it as 'essentially linear with a small logarithmic surcharge', the sweet spot for large-scale processing.