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.
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.
Top comments (0)