CODEWITHSUNDEEP
algorithmbig-otime-complexity
JC.
JC.

Reputation: 639

Comparison Sorting Algorithm Complexity

Why is the lower bound for the time complexity of comparison-based sort algorithms O(n log n)?

Upvotes: 3

Views: 3719

Answers (2)

Brad
Brad

Reputation: 5488

In short, because you must look at every element which is O(n). For each of those elements you look at, you must find out if its in the right order, which is at best O(log n) (binary search for example). So the net sum becomes O(n log n)

Upvotes: 1

meriton
meriton

Reputation: 70564

http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list

answers that question quite well, I think.

Upvotes: 7

Related Questions