Template talk:Infobox algorithm

Complete?

Does anyone know if the term "complete" (in this sense) is widely used? I'm having a hard time finding any other references to it outside of Wikipedia. I think including it in this table is just confusing, especially with the other meanings of the word. Broken Segue 11:05, 23 April 2008 (UTC)[reply]

Speaking of which, can anybody make out what "optimal" means? -- Smjg (talk) 14:18, 10 April 2009 (UTC)[reply]

Meaning: it is proven to be run at the lower bound of all possible algorithms to solve this given problem. John Sheu (talk) —Preceding undated comment added 03:48, 18 April 2009 (UTC).[reply]

Merge Sort's best case is O(n)??

The box says the best case runtime for merge sort is O(n). I am pretty sure that is wrong. The runtime is *always* O(nlogn). —Preceding unsigned comment added by 98.232.181.18 (talk) 20:10, 5 June 2009 (UTC)[reply]

Darkhan Shalgynbayev (talk) 08:51, 9 June 2009 (UTC): The Mergesort Algorithm’s time efficiency is in ϴ(nlogn) in all cases [Anany Levitin. Introduction to The Design and Analysis of Algorithms, 2nd Edition. Addison Wesley, 2007. p.155]. So, I agree with opposed argument![reply]

Animation could be improved with colored background.

Use one color to show the region of the image currently being sorted. Use two other colors to show which two regions are being merged. Would be nice if it were a bit slower, too. Dave Yost (talk) 19:53, 10 July 2009 (UTC)[reply]

Optimality definitons unnecessary and illogical?

I find the "Optimal" entry confusingly ill-defined. Bogosort is "Optimal: No". Heapsort is "Optimal: Never". Quicksort is "Optimal: Sometimes". Is this trying to imply that Heapsort is inferior to Bogosort? What criteria are being used to judge these? What are the possible responses? It's not feasible to assert that the optimality of a single algorithm can be stated for all possible cases. Shouldn't the optimality of an algorithm be considered more fully in the article itself, for given cases? Isn't it enough to list the best/average/worst time/space complexities? If my primary objective is to entertain, would I be remiss in changing Bogosort to "Optimal: Hilarious"? —Preceding unsigned comment added by 141.195.226.101 (talk) 22:29, 18 October 2009 (UTC)[reply]

I agree, the optimal parameter doesn't seem to have been very well thought out and the lack of documentation appears to have led to a ridiculous number of whimsical variants. I suggest the choices Yes for it is an asymptotically optimal algorithm and No for it isn't. Does anyone really have a good reason for middle ground? About the best example would be quicksort which is currently Optimal: Sometimes but seems like (using the standard of worst case analysis) would be Optimal: No. Cheers, — sligocki (talk) 03:33, 17 November 2009 (UTC)[reply]

I strongly believe that the "optimal" parameter should be removed from the template. Some of my objections are explained here: Talk:Depth-first_search#Optimality. In short, these are my main objections:

Optimality is not well-defined for algorithms which solve many problems (like BFS/DFS).
Optimality is not well-defined if there are multiple correct solutions, and some are better than others. For instance, BFS might find shorter paths than DFS. Is BFS optimal and DFS non-optimal?
Optimality can be discussed in the article. Putting it along with time and space complexity gives the issue WP:UNDUE WEIGHT.
How many optimal algorithms do we have anyway? O(n log n) sorting algorithms are non-optimal, since the best lower bound is linear. We have no natural problems in NP with a super-linear lower bound, so almost all algorithms on Wikipedia are non-optimal. (Except binary search and those algorithms that take linear time for problems where the input must be read.)
Editors interpret the word to mean whatever they feel like, which leads to silly things like Merge sort being optimal, Heapsort being "never" and Radix sort being "exactly correct".

Let's get rid of this confusing parameter. Robin (talk) 04:58, 17 November 2009 (UTC)[reply]

I support Robin's proposal per the discussion we've been having at Talk:Depth-first search. —David Eppstein (talk) 05:03, 17 November 2009 (UTC)[reply]

It seemed to me that optimal meant worst case, not best case, so all O(n log n) sorting algorithms are provably optimal. However, I agree that this parameter doesn't seem to have much good purpose and plenty of bad uses. I support getting rid of it. Cheers, — sligocki (talk) 00:12, 18 November 2009 (UTC)[reply]

Well, I've gotten rid of it. About optimality, O(n log n) sorting algorithms are not known to be optimal because we don't have an Ω(n log n) lower bound for sorting in the standard RAM model or the Turing machine model. The Ω(n log n) lower bound is in the decision tree model. The best lower bound known for sorting is just Ω(n). --Robin (talk) 00:43, 18 November 2009 (UTC)[reply]