4 ms·
Some algorithms, such as the famous Knuth Shuffle, are a sequential algorithm in the worst-case scenario. This slide-deck however, demonstrates that the Knuth S
by dragontamer 7y ago
Some algorithms, such as the famous Knuth Shuffle, are a sequential algorithm in the worst-case scenario. This slide-deck however, demonstrates that the Knuth Shuffle is in fact highly parallel in the average case.
In the average case, the dependency graph of a random shuffle is O(log(n)). An infinitely parallel machine would only need O(log(n)) steps to complete a Knuth Shuffle, on the average.
This, and many other "sequential" algorithms, arguably have a "parallel in the average" form waiting to be discovered.