kyb,
see the discussion of quicksort on the other thread. Randomness is used to protect against worst-case behavior, but it’s not because we’re afraid of intelligent adversaries. It’s because worst-case behavior for quicksort happens a lot. If we had a good description of naturally occurring lists, we could design a deterministic pivot algorithm, but we don’t. We only have the observation simple guess-the-median algorithms perform badly on real data. It’s not terribly surprising that human-built lists resonate with human-designed pivot algorithms; but the opposite scenario, where the simplex method works well in practice is not surprising either.
kyb, see the discussion of quicksort on the other thread. Randomness is used to protect against worst-case behavior, but it’s not because we’re afraid of intelligent adversaries. It’s because worst-case behavior for quicksort happens a lot. If we had a good description of naturally occurring lists, we could design a deterministic pivot algorithm, but we don’t. We only have the observation simple guess-the-median algorithms perform badly on real data. It’s not terribly surprising that human-built lists resonate with human-designed pivot algorithms; but the opposite scenario, where the simplex method works well in practice is not surprising either.