[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhbogo_sort.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "bogo sort" source: https://www.jemoka.com/posts/kbhbogo_sort/ --- Bogo sort! Consider an algorithm that randomly shuffles the list, check if the list is sorted, and return. additional information Expected Running Time The expected running time is the number of iterations (\(n!\), in expectation) times the time per iteration (\(n\)). So the expected running time is \(O\qty(n n!)\). Worst Case Running Time Infinite (i.e. if randomness is fixed it will take forever). Some Expectations of Bogo Sort Characteristics Let \(X_{i} = 1\) if \(A\) is sorted after iteration \(i\), \(0\) otherwise. Assuming distinct entries, then \(\mathbb{E}[X_{i}] = \frac{1}{n!}\) (because your list has \(n\) things, so the chance of any given shuffling being sorted is \(\frac{1}{n!}\).) And the expected number of runs until its sorted is \(n!\) per geometric distribution.