DEV Community

Yoshi
Yoshi

Posted on

Intuitive Explanation of O(n log n) Complexity⏳

The time complexity of linear search is O(n), and quadratic time complexity is represented as O(n^2), which are relatively easy to understand. However, for algorithms that use the divide and conquer approach, such as merge sort, the time complexity is O(n log n), which might be a bit confusing. In fact, I was puzzled myself. So, I'd like to explain it using a simple example and a diagram to make it more intuitive than a purely text-based explanation.

a simple example

The log n Part

First, log n represents the number of times the data is divided until there are only pairs of elements left. In divide and conquer algorithms like merge sort or quick sort, the data is repeatedly split into smaller problems. In the diagram above, 8 elements are divided 3 times, so log(8) = 3, which corresponds to 3 levels of division.

The n Part

Next, n represents the number of elements that need to be scanned at each level of division. Since each level processes all n elements, a linear amount of work is needed for each level.

Summary

Thus, the reason why the time complexity of divide and conquer algorithms is O(n log n) can be intuitively understood by combining the log n division levels with the n elements scanned at each level. I hope this diagram helps make the time complexity of divide and conquer algorithms easier to understand. Although it’s a basic topic, I hope it helps someone.

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read full post →

Top comments (0)

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay