Why is O(N) sorting impossible?

What is the fastest sorting algorithm known to man? We find out by attempting to find an O(n) time complexity sorting algorithm. Till now, the research on sorting has found O(n*log(n)) to be the best.

We discuss concepts of time complexity, decision making and how the best algorithm is bounded by the permutation tree of an array. A final trick is used to bring down the complexity to O(N)!

N! Approximation: https://en.wikipedia.org/wiki/Stirling%27s_approximation

log(N) video: https://www.youtube.com/watch?v=Xe9aq1WLpjU&vl=en

System Design Video Course:
https://get.interviewready.io

Along with video lectures, this course has architecture diagrams, capacity planning, API contracts and evaluation tests. It’s a complete package.

Use the coupon code ‘earlybird’ for a 20% discount.

Sources:
https://hackernoon.com/timsort-the-fastest-sorting-algorithm-youve-never-heard-of-36b28417f399
https://stackoverflow.com/questions/3969813/which-parallel-sorting-algorithm-has-the-best-average-case-performance
https://stackoverflow.com/questions/2352313/is-there-an-on-integer-sorting-algorithm

#sorting #algorithm #sortingalgorithm