[macosxnerd101]

Quote

Let me address something right now. According to Wikipedia, Rice's theorem says: for any non-trivial property of partial functions, there is no general and effective method to decide whether an algorithm computes a partial function with that property.

More formally, Rice's Theorem states that given a subset C of Recursively Enumerable languages, where C is non-empty and C is not RE (the set of all recursively enumerable languages), then C is undecidable. In a sense, this means that any non-trivial property is not decidable.

[ishkabible]

the N*lg(N) time bounds is for comparison based sorting algorithms and is a bound on establishing the number of comparisons that need be made for an order to be formed. Non-comparison based algorithms and hybrids don't follow the same rules. More over you should note that radix sort is O(l*n) where 'l' is the length of what you are sorting. for integers this is really small (if say a byte is used as the key) but for a string or something this is quite large and lg(n) can be much smaller than l. l on the other hand can be smaller for small integers and the like.

edit:
well I'm apparently tired and didn't see that there were more pages (4 more to be exact) sorry for the lack of coherency in this post and potential restatement of stuff which has already been said.

This post has been edited by ishkabible: 31 December 2013 - 12:48 AM