A linearithmic function grows in proportion to the input size multiplied by its logarithm: O(n * log(n)). Its growth accelerates as inputs grow, but remains far slower than quadratic or exponential growth. section 4.8
Use the growth class to compare how algorithms behave as inputs become larger:
- It grows faster than logarithmic and linear functions, so additional input increases the running time by increasingly larger amounts. section 4.8
- It remains manageable for large inputs compared with quadratic functions, which become impractical much sooner. section 4.9
- It commonly describes efficient sorting algorithms and the behavior of priority queues. section 4.9 section 4.16
Choosing a sorting algorithm
For a billion-element array, a linearithmic algorithm such as mergesort or heapsort is described as manageable, while quadratic selection sort would take an impractical amount of time. section 4.9
Some of the growth rates you might encounter when studying algorithms. From left to right, the functions grow increasingly faster.
A growth-rate figure makes the relative acceleration of linearithmic, quadratic, and faster function classes easier to compare visually. section 4.8
