Linearithmic Time: O(n log n)

Grokking Algorithm Complexity and Big-O

Ask Author

Back to course home

0% completed

Vote For New Content

Linearithmic Time: O(n log n)

Table of Contents

Contents are not accessible

Linearithmic Time Complexity $O(n \log n)$ occurs when an algorithm combines linear processing with a logarithmic operation at each step. This often arises in algorithms that sort data and then perform binary search or other divide-and-conquer tasks. The $O(n \log n)$ complexity is common in sorting-based algorithms and efficient searching methods.

Key Characteristics

In an algorithm with $O(n \log n)$ time complexity:

The input is first processed linearly (such as sorting).
Each element undergoes a logarithmic operation, typically through binary search or repeated division.

In an algorithm with $O(n \log n)$ time complexity:

Code Example: Sorting and Searching Elements

The following code uses an $O(n \log n)$ approach to check for the presence of each target in a list. The list is first sorted, allowing binary search (which operates in $O(\log n)$ time) to efficiently check for each target.

Python3

. . . .

Explanation:
- The check_elements function first sorts arr, which requires $O(n \log n)$ time.
- After sorting, the binary_search function checks each target in targets for membership in arr.
- Binary search operates in $O(\log n)$ time for each search, and since there are $k$ targets, this phase has a time complexity of $O(k \log n)$ .

Total Time Complexity

Sorting the array takes $O(n \log n)$ .
For each target, binary search takes $O(\log n)$ , so searching all $k$ targets takes $O(k \log n)$ .
If $k \approx n$ , the combined time complexity is $O(n \log n) + O(n \log n) = O(n \log n)$ .

Examples of $O(n \log n)$ operations

Sorting and Searching: As demonstrated, sorting an array first, then using binary search to find specific elements.
Balanced Tree Insertion: Building a balanced tree with $n$ elements requires $O(n \log n)$ time as each insert is $O(\log n)$ .
Recursive Merging of Data: Merging large sets of sorted data in chunks, where sorting is combined with merging, often leads to $O(n \log n)$ complexity.

.....