Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Of course an O(N) method will beat an O(NlgN) method, because O(N) < O(NlgN).

Radix sort is a linear time sort because the hardware (random access memory) is built to allow constant-time lookup of memory. Radix sort wouldn't be linear time on a sequential access memory system, like tape, but merge sort would still be O(NlgN) on such a system.



It doesn't invalidate what you say, but you're assuming there's a bounded number of different values in the array -- 2^k where k is your word size.

Under this assumption, a correctly implemented quicksort also runs in O(N) time.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: