[Solved]: When can one use a $O(n)$ time sorting algorithm?

Problem Detail: 

Some sorting algorithms like counting sort/insertion sort can work in $O(n)$ time while other algorithms such as quicksort require $O(n \log n)$ time.

As I understand it, it's not always possible to use the $O(n)$ sorting algorithms. What are those cases when they can not be used?

Asked By : user6821

Answered By : Shaull

In the comparison model, where all you are allowed to do is to compare two elements, and without further assumptions, we can prove that no sorting algorithm can do better than $O(n\log n)$.

If you want to sort in $O(n)$, you need either a stronger model, or additional assumptions.

For example, if you can bound the range of the numbers you are sorting, you can use bucket-sort, which is $O(n)$ (time).

A different example is spaghetti-sort: if you can implement the $\max$ function over $n$ elements in $O(1)$, then you can sort in $O(n)$.

You see here that different assumptions can allow you to sort in $O(n)$. There is no characterization of exactly which assumptions allow it.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9965

3.2K people like this

 Download Related Notes/Documents