Remix.run Logo
krackers a day ago

Maybe for very high-level intuition, it's vaguely similar to other randomized algorithms that you want to minimize the worst-case on expectation and the easiest way to do so is to just introduce randomness (think quicksort, which is N^2 worst case with a badly chosen pivot). Your idea of there being an optimal distance is similar to the concept of "derandomization" maybe, e.g. in Quicksort there are deterministic pivot selection algorithms to avoid the worst case. But all of those require much more effort to compute and require an algorithm whose output is a function of the input data. Whereas randomly picking a pivot or randomly creating express lanes is simpler and avoids the data dependency (which is important since unlike sorting, the data isn't fixed ahead of time).