3 ms·
Unfortunately, randomly permuting the input takes O(nlog(n)) steps (you need at least this much time just to read in sufficiently many random bits). Perhaps a c
by cevi 5y ago
Unfortunately, randomly permuting the input takes O(nlog(n)) steps (you need at least this much time just to read in sufficiently many random bits). Perhaps a clever parallel architecture could reduce the runtime?
- deleted 5y ago[deleted]
- michaelmior 5y agoThis is not true if you can generate a random number in constant time which is probably the more practical of the constraints to satisfy when implementing this algorithm.