Linearithmic function
A linearithmic function has growth proportional to the product of an input size and its logarithm.
Advanced Algorithms and Data Structures
Linearithmic time is a running-time complexity proportional to the product of the input size and its logarithm.
- How it is used
- Analyzes the cost of constructing a balanced k-d tree from a known set of points.
- 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 you can do after
- Evaluate/understand when recursive tree construction has O(n log(n)) time and O(n) space.
Read how Advanced Algorithms and Data Structures explains linearithmic function →
Grokking Data Structures
Linearithmic growth is growth proportional to the product of input size and its logarithm.
- How it is used
- Classifies algorithm running times and memory growth as input sizes increase.
- How deep it goes
- Defines O(n * log(n)) and compares its acceleration with logarithmic, linear, quadratic, and exponential growth.
- Examples
- Uses mergesort and heapsort as linearithmic examples, contrasting them with quadratic selection sort.
- What you can do after
- Evaluate algorithm choices by comparing linearithmic growth with slower and faster asymptotic classes.
Read how Grokking Data Structures explains 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²).
- functionkind of · A function is a defined operation that maps inputs to outputs and, when implemented as a callable program unit, may also produce effects.
- 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.
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.