A linearithmic running time grows in proportion to n log(n). In balanced k-d tree construction, partitioning the points costs O(n), while two recursive half-sized subproblems produce Tₖ(n) = 2Tₖ(n/2) + O(n) = O(n log(n)). section 9.3.3
Linearithmic function
Linearithmic time is a running-time complexity proportional to the product of the input size and its logarithm.
How Advanced Algorithms and Data Structures covers it
- How deep it goes
- Derives O(n log(n)) from a divide-and-conquer recurrence and pairs it with O(n) space.
- Examples
- Uses median-based k-d tree construction and concrete point partitions to illustrate the recurrence.
- What it assumes
- Assumes familiarity with balanced trees, recursion, tree height, and asymptotic running time.
- What you can do after
- Evaluate/understand when recursive tree construction has O(n log(n)) time and O(n) space.
- How it connects
- Connects balanced trees, k-d trees, recursion, logarithmic time, and divide-and-conquer recurrences.
Also explained in
-
Grokking Data StructuresLinearithmic growth is growth proportional to the product of input size and its logarithm.
Compare how 2 books explain linearithmic function →
Related concepts
- growth ratekind of · A growth rate describes how rapidly a function or resource requirement increases as its input increases.
- 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²).
- priority queuemeasured by · A priority queue is an abstract data type that retrieves or removes elements according to assigned priority rather than insertion order.
- logarithmcontrasts with · A logarithm is the exponent to which a specified positive base other than one must be raised to produce a given positive number.
This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.