Talk:Asymptotically optimal algorithm

Add topic
Active discussions
WikiProject Computer science (Rated Start-class, Mid-importance)
WikiProject iconThis article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start This article has been rated as Start-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
Things you can help WikiProject Computer science with:

Article nameEdit

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 paperEdit

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???Edit

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 computationEdit

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