Talk:Asymptotically optimal algorithm

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)

Please provide link to example paper

Taken from the current article:

Another is the resizable array data structure published in "Resizable Arrays in Optimal Time and Space", which can index in constant time but on many machines carries a heavy practical penalty compared to ordinary array indexing.

There should be a reference to this example paper, "Resizable Arrays in Optimal Time and Space". Either an ACM Portal link, CiteSeer link, or more information such as publication date and author. It sounds like a good example, but it should be referenced appropriately. -- anonymous

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)

Model of computation

The article severely lacks the discussion of the model of computation, without clear understanding of which all the reasoning lacks rigor. Although intuitively clear, it may lead to inherent problems when someone tries to get some deeper undertanding. This is already seen from the discussion in this talk page. I added a sentence, but this requires further elaboration. `'mikka