On 14/12/08 02:22, Ben Schmidt 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.
>> 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.
...or even a bounded number of times (i.e., the number of times might be
variable, but it admits a fixed upper bound independent of n).
Best regards,
Tony.
--
No violence, gentlemen -- no violence, I beg of you! Consider
the furniture!
-- Sherlock Holmes
--~--~---------~--~----~------------~-------~--~----~
You received this message from the "vim_use" maillist.
For more information, visit http://www.vim.org/maillist.php
-~----------~----~----~----~------~----~------~--~---
