What does O(n log n) signify in algorithm analysis?

The notation O(n log n) signifies a combination of linear and logarithmic time complexity. This means that the growth rate of the algorithm's running time is proportional to the product of n (the size of the input) and log n (the logarithm of the input size).

In practical terms, when you have an algorithm that runs in O(n log n) time, it suggests that as the input size increases, the time taken grows faster than linear time complexity (O(n)) but slower than quadratic time complexity (O(n^2)). This type of complexity is commonly seen in efficient sorting algorithms, such as mergesort and heapsort, which exploit a divide-and-conquer approach where the input is divided logarithmically and requires a linear amount of work to combine the results.

Understanding this complexity is crucial for assessing algorithm efficiency, as it helps to choose the right algorithm based on the size of the data being processed.