Talk:Asymptotically optimal algorithm

This 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.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

Mid

This article has been rated as Mid-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Article name[edit]

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)[reply]

Please provide link to example paper[edit]

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)[reply]

Model of computation[edit]

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