What that tells me is that the current metric we use for problem complexity (e.g. big-o) is woefully inadequate at measuring the actual complexity of problems.
> the current metric we use for problem complexity (e.g. big-o) is woefully inadequate at measuring the actual complexity of problems.
The complexity of all problems. But big-O isn't the only complexity metric available.
It's extremely useful and very adequate in almost all cases, but it doesn't work well when the numbers are very small and the problems are part of a small subset of all available problems.
But those are edge cases. In practice those are fairly rare and when the datasets are small enough normally all solutions are more or less viable. But as soon as your data set is non-trivial big-O is the right tool to apply at the outset.
Right tool for the job... small dataset, tricky problem: big-O may not apply.
Why would they be inadequate? They are a very good metric that lets one instantly recognize the way the problem’s certain properties change with respect to some other factor. Does it give a complete picture for everything? No. Why would it? But to say that they are woefully inadequate is just ridiculous.
Lots of CS theorists are working on non worst case analysis and have been for some time. The CS research community recognizes the limitations of worst case.
It makes sense to teach worst case in undergrad classes because it's easier to understand and basically a prerequisite for other kinds of analysis.
The complexity of all problems. But big-O isn't the only complexity metric available.
It's extremely useful and very adequate in almost all cases, but it doesn't work well when the numbers are very small and the problems are part of a small subset of all available problems.
But those are edge cases. In practice those are fairly rare and when the datasets are small enough normally all solutions are more or less viable. But as soon as your data set is non-trivial big-O is the right tool to apply at the outset.
Right tool for the job... small dataset, tricky problem: big-O may not apply.