Talk:Sorting algorithm: Difference between revisions

Revision as of 17:25, 22 June 2020

Revision as of 17:47, 22 June 2020

Line 1,113:

I would like to discuss a revert done by an anonymous IP. The reason for the revert was that the expected runtime is given in the average case. This is, however, wrong. The expected runtime is different from the average case. These two names are different concepts: the average case is a description of the input. The input meaning here the list to sort. We assume some distribution of the input and calculate the expectation for the runtime over this distrubtion. This is different for "expected runtime". The 'expected' in 'expected runtime' does not relate to the input, but instead to what we often call 'random bits'. The 'random bits' are not part of the input (this would make the whole concept of probablistic programming ad absurdum). Therefore we can not say that the average-case is identical to the expected runtime. We have infinitely many expected runtimes, especially we have a worst-case expected runtime, a best-case expected runtime and again we also have an average-case expected runtime.

Even worse, saying that the worst-case runtime of bogosort is infinite is at best misleading and at worst a critical error. That is because there is really no concept in which infinite would be a meaningful runtime for bogosort. I would accept using the phrase 'certainly unbounded', meaning assuming that there is no randomess, the runtime is not bounded by any function depening on the input. Even saying that the runtime is unbounded (without using the word certainly) is misleading as the probability for unbounded runtime is 0 and even the expected runtime is at most n x !n. I would therefore ask to redo my change to fit more with the given source (which uses the same semantics) and with the current research. --[[User:PhoenixIra|PhoenixIra]] ([[User talk:PhoenixIra|talk]]) 17:25, 22 June 2020 (UTC)