O(n * log n)
O(n log n) is an asymptotic growth rate in which computation increases proportionally to the input size multiplied by its logarithm.
Grokking Algorithms, Second Edition
O(n * log n) is a time-complexity bound whose operation count grows as the input size multiplied by its logarithm.
- How it is used
- Compares algorithm growth rates and analyzes sorting performance, especially merge sort and quicksort.
- How deep it goes
- Explains the bound through per-level work and call-stack height, then distinguishes guaranteed, average, and worst-case behavior.
- Examples
- Uses merge sort, quicksort, selection sort, estimated growth charts, and balanced partition levels as concrete examples.
- What you can do after
- Evaluate sorting algorithms by recognizing O(n log n) growth and separating average-case from worst-case performance.
Read how Grokking Algorithms, Second Edition explains O(n * log n) →
Clojure: The Essential Reference
O(n log n) complexity is an asymptotic growth rate in which computation increases proportionally to input size times its logarithm.
- How it is used
- Guides performance review when applying sort or sort-by to Clojure collections, especially large datasets.
- How deep it goes
- Explains steps, memory, Timsort, ordered segments, insertion sort, and merging.
- Examples
- Uses Clojure sort results, large-dataset guidance, chunked parallel sorting, and performance comparisons by input ordering.
- What you can do after
- Evaluate sorting performance and recognize when collection size makes sort or sort-by noticeably slower.
Read how Clojure: The Essential Reference explains O(n * log n) →
Related concepts
- quicksortmeasures · Quicksort is a comparison-based sorting algorithm that partitions elements around a pivot and recursively sorts the resulting subranges.
- merge sortmeasures · Merge sort is a comparison-based sorting algorithm that recursively divides a sequence and merges the resulting sorted subsequences.
- sorting algorithmmeasures · A sorting algorithm is a procedure that rearranges elements of a collection into an order determined by an ordering criterion.
- quadratic time complexitycontrasts with · Quadratic time complexity is an asymptotic running-time growth rate proportional to the square of input size, commonly denoted O(n²).
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.