Aram Havarneanu wrote: > David Hláčik <[email protected]> wrote: >> 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. Though it depends a little how you measure. However, since we are just sorting numbers, I'd say an access to the count array should be counted equally to an access to the array being sorted. Not that I have an alternative proposal at this stage... Ben. --~--~---------~--~----~------------~-------~--~----~ You received this message from the "vim_use" maillist. For more information, visit http://www.vim.org/maillist.php -~----------~----~----~----~------~----~------~--~---
