Scott, I don't dispute what you say. I just suggest that the confusing term "in the worst case" be replaced by the more accurate phrase "supposing that the environment is an adversarial superintelligence who can perfectly read all of your mind except bits designated 'random'".
While this is an accurate characterization of what the term technically means, it does not really capture all the reasons why worst-case complexity is studied. I would say worst-case complexity is studied because
It allows more general statements, since the statement does not have to be conditioned on an input distribution
For many problems, both efficiently solvable as well as "hard", the average-case complexity is not really different from the
While this is an accurate characterization of what the term technically means, it does not really capture all the reasons why worst-case complexity is studied. I would say worst-case complexity is studied because
- It allows more general statements, since the statement does not have to be conditioned on an input distribution
- For many problems, both efficiently solvable as well as "hard", the average-case complexity is not really different from the
... (read more)