= 27d567bc2d48d9f40e9ccc20ea370b15)
datadataeverywhere comments on How Many LHC Failures Is Too Many? - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (130)
A uniform randomization may not be possible but you can get an arbitrarily well randomized list in linear time. That is all that is needed for the purposes of the sorting. (You would just end up destroying the world 1 + (1 / arbitrarily large) as many times as with a uniform distribution.)
Algorithms like a modified Fisher-Yates shuffle in linear time if you're just measuring reads and writes, but O(lg(n!)) > O(n) bits are required to specify which permutation is being chosen, so unless generating random numbers is free, shuffling is always O(n log n) .
In real life, we don't use PRNGs with sufficiently long cycle times, so we usually get linear-time shuffles by discarding the vast majority of the potential orderings.