Re:A ride that takes 10^20k years to complete in Roller Coas...
by red0point on Monday August 03, 2020 @07:08PM
(#24044567)
Sure you can use Big O, just look at it as the expected runtime. For example, QuickSort is O(n^2) in worst case, but expected O(nlog(n)).
[ Parent
| on HN ]
Re:A ride that takes 10^20k years to complete in Roller Coas...
by leapis on Monday August 03, 2020 @08:01PM
(#24044986)
For probabilistic algorithms, we can look at the worst-case-w.h.p runtime: that is, a randomized quicksort, although technically still having an "absolute" worst case of O(n^2), actually is considered to have a worst case of O(nlog(n)), with probability 1 - 1 / (n^c) when bounded by Chernoff, as shown here: https://web.cs.hacettepe.edu.tr/~ozkahya/classes/bbm402/Lect...