It's a pretty canonical example actually. I immediately thought of quicksort's worst case vs average case when I got to the end of the debate. It's taught in many intro to algorithms courses. (But I sure didn't know about the Kolmogorov complexity part!)