Talk:Asymptotically optimal

From Wikipedia, the free encyclopedia

[edit] Article name

In case anyone wonders, I realise that the name of this article is not a noun or noun phrase, which violates the naming convention. In this case however I believe this is justified, because the phrase "asymptotically optimal" is by far more common than any noun rendering of this phrase, such as "asymptotic optimality". (links are Google searches) Deco 00:16, 1 December 2005 (UTC)

[edit] Better algorithms than merge sort???

Taken from the current article:

As a simple example, it's known that all comparison sorts require Ω(n log n) time. Mergesort and heapsort are comparison sorts which operate in O(n log n) time, so they are asymptotically optimal in this sense (although there are sorting algorithms with better asymptotic performance, they are necessarily not comparison sorts).

Which sorting algorithm has better asymptotic performance than merge sort? Was the author thinking of Radix sort? [But which needs assumptions about the size of the input numbers.] Please clarify what you were thinking! Simon Lacoste-Julien 05:11, 4 April 2006 (UTC)