Talk:Sorting algorithm: Difference between revisions

Revision as of 18:11, 22 June 2020

Revision as of 18:12, 22 June 2020

Line 1,117:

:Worst case is commonly meant to be the worst possible case, which is unbounded for bogosort. The input in this case would commonly include the worst possible random seed as well. At any rate, we follow the sources, and your addition (and the matching addition at [[Bogosort]]) was unsourced. Cite a reputable source and interprets that the worst case behavior as you are and perhaps we can use it. - [[User:MrOllie|MrOllie]] ([[User talk:MrOllie|talk]]) 17:51, 22 June 2020 (UTC)

::I don't agree. Citing CLRS: "The worst-case running time of an algorithm gives us an upper bound on the running time for any input. Knowing it provides a guarantee that the algorithm will never take any longer. We need not make some educated guess about the running time and hope that it never gets much worse." (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press 2009, page 28) and later claryfing: "When analyzing the running time of a randomized algorithm, we take the expectation of the running time over the distribution of values returned by the random number generator. We distinguish these algorithms from those in which the input is random by referring to the running time of a randomized algorithm as an expected running time. In general, we discuss the average-case running time when the probability distribution is over the inputs to the algorithm, and we discuss the expected running time when the algorithm itself makes random choices." (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press 2009, page 117). CLRS also sometimes uses the phrase 'worst-case' complexity when refering to randomized algorithms, when they really mean 'certain worst-case'. Including random bits in the input would also make the runtimes totally absurd: for an infinite runtime, you would need infinite random bits, making an infinite input. This is obviously broken. Again, expectation and worst/average-case are different concepts. Coming to bogosort, we have 'Sorting the slow way: an analysis of perversely awful randomized sorting algorithms': "Let C denote the number of comparisons carried out by bogo-sort on a given input x of length n. Then E(C) = (e − 1)n! + n − O(1) in the worst-case" (Gruber, H.; Holzer, M.; Ruepp, O., "Sorting the slow way: an analysis of perversely awful randomized sorting algorithms", 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007 (PDF), Lecture Notes in Computer Science, 4475, Springer-Verlag, pp. 183–197, Corollary 10).Again, I am on board with using the phrase "unbounded certainl runtime" and "n x !n expected runtime", however, infinite is wrong and don't mentioning the worst-case expected runtime is bad. --[[User:PhoenixIra|PhoenixIra]] ([[User talk:PhoenixIra|talk]]) 18:11, 22 June 2020 (UTC)

the probability distribution is over the inputs to the algorithm, and we discuss the expected running time when the algorithm itself makes random choices." (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press 2009, page 117). CLRS also sometimes uses the phrase 'worst-case' complexity when refering to randomized algorithms, when they really mean 'certain worst-case'. Including random bits in the input would also make the runtimes totally absurd: for an infinite runtime, you would need infinite random bits, making an infinite input. This is obviously broken. Again, expectation and worst/average-case are different concepts. Coming to bogosort, we have 'Sorting the slow way: an analysis of perversely awful randomized sorting algorithms': "Let C denote the number of comparisons carried out by bogo-sort on a given input x of length n. Then E(C) = (e − 1)n! + n − O(1) in the worst-case" (Gruber, H.; Holzer, M.; Ruepp, O., "Sorting the slow way: an analysis of perversely awful randomized sorting algorithms", 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007 (PDF), Lecture Notes in Computer Science, 4475, Springer-Verlag, pp. 183–197, Corollary 10).Again, I am on board with using the phrase "unbounded certainl runtime" and "n x !n expected runtime", however, infinite is wrong and don't mentioning the worst-case expected runtime is bad. --[[User:PhoenixIra|PhoenixIra]] ([[User talk:PhoenixIra|talk]]) 18:11, 22 June 2020 (UTC)