datadataeverywhere comments on How Many LHC Failures Is Too Many? - Less Wrong

16 Post author: Eliezer_Yudkowsky 20 September 2008 09:38PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (130)

Sort By: Old

You are viewing a single comment's thread. Show more comments above.

Comment author: datadataeverywhere 30 September 2010 02:28:33AM *  2 points [-]

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.