Linearithmic time complexity, written as O(n log n), combines linear and logarithmic growth. It commonly appears in efficient comparison-based sorting algorithms such as merge sort and average-case or worst-case analyses of other divide-and-conquer methods under appropriate assumptions. One common explanation is that an algorithm performs work proportional to n at each of log n levels. In merge sort, the input is repeatedly divided into smaller halves until individual elements remain. This creates approximately log₂ n levels. At each level, the merging process handles a total of n elements, producing approximately n work per level. Multiplying the work per level by the number of levels gives n log n. Linearithmic growth is faster than linear growth but substantially slower than quadratic growth for sufficiently large inputs. It is an important complexity class because many practical sorting algorithms achieve O(n log n) worst-case time. The exact complexity of an algorithm still depends on its recurrence, implementation, and assumptions. Not every divide-and-conquer algorithm is automatically O(n log n); the amount of work performed at each level must be analyzed.
Linearithmic Time Complexity — O(n log n)
Linearithmic complexity commonly occurs when an algorithm performs linear work across logarithmically many levels or stages.
T(n) ∈ Θ(n log n) when the total work is proportional to n for each of Θ(log n) stages.
Explanation
Variables
| Symbol | Meaning | Unit |
|---|---|---|
n | Number of input elements. | Input elements |
log n | Number of logarithmic stages or levels. | Levels |
T(n) | Total running-time function. | Operations or time |
Example or application
Merge sort divides an array of 16 elements into smaller subarrays. It requires approximately log₂16 = 4 levels of division. At each level, merging processes a total of approximately 16 elements. The total work is therefore proportional to 16 × 4 = 64, illustrating n log n growth.
Key Properties
Combines linear and logarithmic growth.
Often arises in divide-and-conquer algorithms.
Merge sort has Θ(n log n) time complexity.
Commonly provides efficient sorting performance for large inputs.
The number of levels and work per level must both be analyzed.
It grows faster than linear but slower than quadratic complexity.
Prerequisites
Understanding of linear complexity.
Understanding of logarithmic complexity.
Basic recursion and divide-and-conquer concepts.
Learning Objectives
Explain the meaning of linearithmic complexity.
Understand why merge sort has n log n growth.
Analyze work performed across recursive levels.
Compare linearithmic complexity with linear and quadratic growth.
Core Concepts
Linearithmic growth
Divide and conquer
Recursive levels
Merging
Recurrence relations
Work per level
Step By Step
Identify whether the algorithm divides the problem into smaller parts.
Determine the number of recursive levels.
Calculate the total work performed at one level.
Determine whether each level performs approximately linear work.
Combine the work across all levels to obtain n log n growth when the conditions apply.
Pseudocode
ALGORITHM MergeSort(A)
IF length(A) <= 1
RETURN A
END IF
middle = floor(length(A) / 2)
left = MergeSort(first half of A)
right = MergeSort(second half of A)
RETURN Merge(left, right)
Complexity
Time
Θ(n log n)
Space
O(n)
Explanation
Merge sort creates logarithmically many recursive levels and performs linear total merging work at each level. Its temporary arrays require linear additional storage in a typical implementation.
Applications
Merge sort.
Heap sort.
Efficient comparison-based sorting.
Divide-and-conquer algorithms.
Large-scale ordering and ranking tasks.
Algorithms that perform linear work over logarithmically many stages.
Common Mistakes
Assuming every recursive algorithm has O(n log n) complexity.
Counting recursive calls without analyzing the work inside each level.
Ignoring the cost of merging or combining subproblems.
Confusing O(n log n) with O(log n).
Assuming time complexity and auxiliary space complexity must have the same growth rate.
Key Takeaways
O(n log n) combines linear work and logarithmically many stages.
Merge sort is a standard example.
Analyzing each recursive level helps explain the complexity.
Linearithmic algorithms are important for efficient sorting and large-data processing.
Related Topics
Logarithmic Time Complexity
Linear Time Complexity
Quadratic and Polynomial Time Complexity
Divide-and-Conquer Algorithms
Recurrence Relations
Limitations
The suitability of linearithmic time complexity — o(n log n) depends on the exact problem requirements and the assumptions made about the input.
An implementation of linearithmic time complexity — o(n log n) can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.
For linearithmic time complexity — o(n log n), evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.
Practice Questions
| Question | Answer |
|---|---|
What is the main purpose of linearithmic time complexity — o(n log n)? | Linearithmic complexity commonly occurs when an algorithm performs linear work across logarithmically many levels or stages. |
What should be checked before applying linearithmic time complexity — o(n log n)? | For linearithmic time complexity — o(n log n), verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of linearithmic time complexity — o(n log n) be validated? | Trace a representative linearithmic time complexity — o(n log n) case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- SCIENEXY Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures