O(n log n) – Linearithmic Time Complexity

byMD Modasshar hussain -
0

 

O(n log n) – Linearithmic Time Complexity

After learning O(1), O(log n), and O(n), it's time to understand another very important time complexity: O(n log n).

At first glance, O(n log n) may look confusing because it combines two mathematical terms: n and log n. But don't worry! Once you understand the idea behind it, you'll realize why many of the fastest sorting algorithms use this complexity.

In fact, O(n log n) is considered one of the most efficient time complexities for solving large-scale problems.

{tocify} $title={Table of Contents}


What is O(n log n)?

O(n log n) means that an algorithm performs log n operations for each of the n elements.

In simple words:

  • The algorithm goes through all the elements.
  • For each element, it performs a logarithmic amount of work.
What is O(n log n)?


Because of this combination, the total work becomes n × log n, which we write as O(n log n).

Although this is slower than O(n), it is still much faster than O(n²) when working with large amounts of data.

Simple Definition

Linearithmic Time Complexity (O(n log n)) means the running time grows slightly faster than linear time because the algorithm processes every element while repeatedly dividing the problem into smaller parts.

Real-Life Example

Imagine you are a teacher checking exam papers for 1,000 students.

Instead of arranging all the papers manually from start to finish, you first divide them into smaller groups.

Then you continue dividing each group until they become easy to organize.

Finally, you combine all the sorted groups together.

This method is much faster than comparing every paper with every other paper.

This is exactly how algorithms like Merge Sort work.

Why is O(n log n) Important?

Many real-world applications need to sort or organize huge amounts of data.

For example:

  • Google sorts billions of search results.
  • Amazon sorts products based on ratings and prices.
  • Netflix organizes movie recommendations.
  • Banking systems sort millions of transactions every day.

If these systems used slower algorithms like O(n²), they would become much slower as the amount of data increased.

That is why most modern sorting algorithms are designed to achieve O(n log n) performance.

Algorithms That Use O(n log n)

Some popular algorithms with O(n log n) time complexity are:

  • Merge Sort
  • Heap Sort
  • Quick Sort (Average Case)
  • TimSort (used in Python)
  • IntroSort (used in C++ STL sort())

These algorithms are preferred because they can efficiently handle very large datasets.

Understanding O(n log n) with Numbers

Suppose we have different input sizes.

Number of Elements (n)log₂(n)Total Operations (n × log₂(n))
8324
16464
325160
646384
1287896
1,0241010,240

Notice something interesting.

When the input doubles, the work does not double dramatically like O(n²).

Instead, it increases gradually, making O(n log n) a practical choice for large applications.

Visual Comparison

Imagine you have 1,000 books that need to be arranged alphabetically.

Method 1

Compare every book with every other book.

This takes a very long time.

Method 2

Divide the books into smaller groups.

Sort each group.

Merge the groups together.

This finishes much faster.

That second method represents O(n log n).

C++ Example Using Merge Sort

#include <iostream>
using namespace std;

void merge(int arr[], int left, int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int L[n1], R[n2];

    for(int i = 0; i < n1; i++)
        L[i] = arr[left + i];

    for(int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];

    int i = 0, j = 0, k = left;

    while(i < n1 && j < n2)
    {
        if(L[i] <= R[j])
            arr[k++] = L[i++];
        else
            arr[k++] = R[j++];
    }

    while(i < n1)
        arr[k++] = L[i++];

    while(j < n2)
        arr[k++] = R[j++];
}

void mergeSort(int arr[], int left, int right)
{
    if(left < right)
    {
        int mid = (left + right) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main()
{
    int arr[] = {40, 20, 70, 10, 90, 50};

    int size = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, size - 1);

    cout << "Sorted Array:\n";

    for(int i = 0; i < size; i++)
        cout << arr[i] << " ";

    return 0;
}

Output

Sorted Array:

10 20 40 50 70 90

Why Does Merge Sort Have O(n log n)?

Merge Sort follows two important steps.

Step 1: Divide

The array is repeatedly divided into two halves.

For example:

40 20 70 10 90 50

↓

40 20 70 | 10 90 50

↓

40 | 20 70 | 10 | 90 50

↓

40 | 20 | 70 | 10 | 90 | 50

Each division cuts the problem into half.

This contributes the log n part.

Step 2: Merge

After dividing, Merge Sort combines the smaller sorted arrays.

During merging, every element is visited once.

This contributes the n part.

Therefore,

Time Complexity = O(n × log n)

= O(n log n)

Another Simple Example

Suppose you have 16 students.

You divide them into two groups.

16

↓

8 + 8

↓

4 + 4 + 4 + 4

↓

2 + 2 + 2 + 2 + 2 + 2 + 2 + 2

↓

1 + 1 + 1 + 1 + ...

The number of divisions is only 4, because:

log₂16 = 4

Now imagine checking every student during every level.

That becomes:

16 × 4

= 64 operations

Which is much smaller than:

16² = 256 operations

O(n log n) vs O(n²)

Input SizeO(n log n)O(n²)
10066410,000
1,0009,9661,000,000
10,000132,877100,000,000

As you can see, the difference becomes huge as the input size grows.

O(n log n) vs O(n²)


This is why software engineers always prefer O(n log n) algorithms whenever possible.

Where Is O(n log n) Used?

You may not realize it, but you use O(n log n) algorithms almost every day.

Some examples include:

  • Sorting files on your computer
  • Organizing photos by date
  • Ranking search results on Google
  • Sorting products on shopping websites
  • Arranging playlists in music apps
  • Banking transaction processing
  • Data analytics and reporting
  • Database indexing
  • Machine Learning data preprocessing

Advantages of O(n log n)

  • Much faster than O(n²) for large datasets.
  • Handles millions of records efficiently.
  • Used in many real-world software applications.
  • Perfect for sorting and divide-and-conquer algorithms.
  • Commonly asked in coding interviews.

Disadvantages of O(n log n)

  • Slightly slower than O(n).
  • Can be more difficult to implement than simple algorithms.
  • Some algorithms require additional memory (for example, Merge Sort).

Quick Revision

  • O(n log n) combines linear and logarithmic growth.
  • It is commonly used in efficient sorting algorithms.
  • Merge Sort, Heap Sort, and the average case of Quick Sort have O(n log n) time complexity.
  • It performs much better than O(n²) for large inputs.
  • Many modern applications rely on O(n log n) algorithms to process large amounts of data quickly.


🧩 Algorithm




Learn algorithms with examples and step-by-step explanations

📘 IT Tech Language




☁️ Cloud Computing
🧩 Algorithm
🤖 Artificial Intelligence (AI)
📊 Data Analyst


🧠 Machine Learning (ML)
🗄️ SQL
💠 C++ Programming


🐍 Python
🌐 Web Development
🚀 Tech to Know & Technology







Tags

You may like these posts

Post a Comment

Ask any query by comments

Previous Post Next Post