Randomization in algorithms, to avoid worst case behavior, would be things like shuffling input, XORing hashes for query parameters per run or per hash table, or using random tiebreakers.
For example there's an easy randomized algorithm to determine a quadratic nonresidue modulo a prime with success probability 1/2 per Legendre symbol evaluation. In expectation this is 2 iterations, and that's independent of the prime. The best known deterministic algorithm takes log(p)^2 such evaluations in the worst case, even assuming generalized Riemann hypothesis.
That seems mistaken to me. The best case in most crypto, from an attacker's perspective, is "I tried one key and just happened to get it right". Aren't we more interested in expected outcomes?
When we are deciding to retire an algorithm it’s often down to how many unaddressed weaknesses there are and assuming that they compose. That’s the best case I was referring to.