There is one way in which we can do O(n). Convert the numbers in base 'n'. [ O(n) ]. Now, there are 2-digit numbers, each digit ranging from 0 to n-1. You can call count-sort 2 times (for each digit), so, complexity is O(n +n) =O(n).
On Jun 27, 12:22 am, Dan <[email protected]> wrote: > Your question is good for a classroom style discussion/debate. > However, in the real world, there is no simple answer. > > There are lots of sorting algorithms. Each one has it's pros & cons > and no single sorting algorithm is "best", especially when not much is > known about the data to be sorted. In your case.... about all that > we really know is that there are no negative numbers involved. I > don't think that helps very much (any?). Then... you need to > consider the programming language and computer system used for the > implementation. Yes. They do matter. Sometimes, they matter a > LOT. Don't assume that an O(x) algorithm is better than an O(y) > algorithm just because x is less than y. > > Dan :-) > > On Jun 26, 12:14 am, ross <[email protected]> wrote: > > > > > > > > > Given a sequence of numbers in the range of 1-N^2, what is the most > > efficient way to sort the numbers (better than NlgN).. > > Can counting sort be used here? Is an O(N) solution possible.. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
