4 ms·

I think this is provably false, probably, since you can compose a pathological case where you have a no-op that adds an O(n) (or more) step to the runtime and a

I think this is provably false, probably, since you can compose a pathological case where you have a no-op that adds an O(n) (or more) step to the runtime and an optimization step that purely removes that no-op. There's optimizations which are tradeoffs against reducing the valid input space (or optimization for the common input cases), and then there's optimizations that eliminate unnecessary operations or combine things cleverly without degrading the worst-case scenario.

AndrewOMartin 10y ago
I'm not immediately convinced by your no-op example because I can conceive of situations that needs a little extra time to be passed between actions, such as in the case of sorting elements whose value isn't easily determinable and is best estimated n clock ticks after the previous action. This is of course a million miles away from the kind of sorting problems you get in Computer Science 101, but this is my point, the traditional sorting problems happen in a very well defined context, as soon as that changes, you might find any algorithm being optimal. Including Bogosort and, for example, quicksort with some extra no-ops. I like your point, but for the reason above I still think the No Free Lunch theorem is valuable, else I wouldn't have had this insight in the first place. At least, I consider it an insight, YMMV.
- rincebrain 10y ago
  Sure, it's certainly valuable to realize that you rarely get an optimization in one case that's not pessimal in another, and it is well-removed from the constrained environments that people work through for demoing algorithms. I was just thinking in terms of more abstract optimization (e.g. platform-agnostic ones that just strictly reduce work to be done) versus platform-specific optimizations/workarounds/bin-packing (like nops to prevent your pipelines or cache lines from being pathological).

AndrewOMartin 10y ago

I'm not immediately convinced by your no-op example because I can conceive of situations that needs a little extra time to be passed between actions, such as in the case of sorting elements whose value isn't easily determinable and is best estimated n clock ticks after the previous action. This is of course a million miles away from the kind of sorting problems you get in Computer Science 101, but this is my point, the traditional sorting problems happen in a very well defined context, as soon as that changes, you might find any algorithm being optimal. Including Bogosort and, for example, quicksort with some extra no-ops. I like your point, but for the reason above I still think the No Free Lunch theorem is valuable, else I wouldn't have had this insight in the first place. At least, I consider it an insight, YMMV.

rincebrain 10y ago
Sure, it's certainly valuable to realize that you rarely get an optimization in one case that's not pessimal in another, and it is well-removed from the constrained environments that people work through for demoing algorithms. I was just thinking in terms of more abstract optimization (e.g. platform-agnostic ones that just strictly reduce work to be done) versus platform-specific optimizations/workarounds/bin-packing (like nops to prevent your pipelines or cache lines from being pathological).