2 ms·
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 b
by castratikron 10y ago
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.
- hnkain 10y agoIt 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.