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!)
reference
Wow, they say exactly the same things I do, right down to using quicksort as an example.
I assumed you were aware of that paper. If you came up with that result independently, then kudos to you ;)
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!)