Linearithmic Time: O(n log n)

Grokking Algorithm Complexity and Big-O

Ask Author

Back to course home

0% completed

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.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible