2 ms·
One possible answer is that any algorithm can be sped up linearly: https://en.m.wikipedia.org/wiki/Linear_speedup_theorem https://en.m.wikipedia.org/wiki/Linear
by Jaxan 7y ago
One possible answer is that any algorithm can be sped up linearly: https://en.m.wikipedia.org/wiki/Linear_speedup_theorem https://en.m.wikipedia.org/wiki/Linear_speedup_theorem . (At least theoretically, for runtimes bigger than linear.)
Another answer could be Moore's law: machines do get faster over time. (And also memory gets cheaper.) And so we wish to define efficiency (time or space) in a way which does not depend on the current technological state.
- dooglius 7y agoThat theorem just indicates that Turing Machines with an unbounded/arbitrary number of symbols is a poor model; the approach there will not work on any actual machine. If you take out a factor of 2 in an algorithm, that's going to asymptotically double the state regardless of what actual machine you're on, so I don't buy machine-independence as a reasonable excuse. The actual reason constants are ignored is because it makes the math a lot simpler when you ignore them.