>>>> I have to create stable algorithm for sorting n numbers from interval >>>> [1,n^2] with time complexity O(n) . >>> Count sort? >>> >>> http://en.wikipedia.org/wiki/Counting_sort >>> >>> It's time complexity is O(n), but space complexity in your case is O(n^2). >> I would say it's not O(n). It has to iterate the count array, so it's >> O(n^2) in this case. > > I've never seen an algorithm for sorting that's better than O(n log n) > on average. Are there any?
Not in general, but in specific cases. In this case, the counting sort complexity is O(n^2) because the numbers are from the set [1,n^2] If we were sorting n numbers from [1,n] then the complexity would be O(n). > I can't even imagine how a sort could > possibly be done in O(n) time, since that would require looking at > each element only once... Well, it would require looking at each element only a constant number of times. Ben. --~--~---------~--~----~------------~-------~--~----~ You received this message from the "vim_use" maillist. For more information, visit http://www.vim.org/maillist.php -~----------~----~----~----~------~----~------~--~---
