Linearithmic Time

O(n\log n) means the running time grows a little faster than linearly but much slower than quadratic time. It usually appears when an algorithm repeatedly splits a problem into smaller pieces or uses a balanced tree-like process, so each of the n items is handled across about log n levels of work. In comparison sorting, this is the best typical performance you can get without using extra information about the data, because each comparison gives only limited information and the algorithm needs enough comparisons to determine the full order.

Use this to describe algorithms that sort or process data by repeatedly dividing it, combining subresults, or maintaining balanced structures. It is especially relevant for efficient comparison-based sorting methods and for many divide-and-conquer routines.

• Treating log n as a constant instead of a slowly growing factor
• Confusing O(n\log n) with O(log n) because both involve logarithms
• Assuming all sorting algorithms have this runtime, even though some common ones are slower