On 02/10/2014 04:20 AM, Sturla Molden wrote:
In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower bound on the complexity.
Only true for sorting that involve comparison. However, sorts that use the values of the inputs as positional keys have a lower bound complexity (omega) of O(n) and a worst case complexity of O(n) and are thus asymptotically optimal. For example, given a range of integers guaranteed to be within the range of j to k (lower to higher), one can created a bit field to represent all possible values of j to k. Then, as values are read in, the corresponding but is set true. You have to process the list of n elements once to read it in, and then a second time to read them out in order. This is a 2n operation which is O(n). For very large ranges of j to k, this is impractical and we resort to things like hashing functions which can perform better than n log n sorting algorithms. But there are lots of real world applications where inputs-as-keys works just fine, such as short dispatch tables in operating systems where the value to be sorted represents a process priority, for example. -- ---------------------------------------------------------------------------- Tim Daneliuk tun...@tundraware.com PGP Key: http://www.tundraware.com/PGP/ -- https://mail.python.org/mailman/listinfo/python-list
