3 ms·
Some Sequential Algorithmsare Almost Always Parallel (PDF 2017)
- dragontamer 7y agoSome 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.