News for hackers. Stuff that matters.

A comment on Big O Notation – Using not-boring math to measure code’s efficiency. Parent comment

Re:Big O Notation – Using not-boring math to measure code’s ... by Jaxan on Friday August 02, 2019 @09:29AM (#20592747)
One possible answer is that any algorithm can be sped up linearly: 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.

[ Parent | on HN ]
Re:Big O Notation – Using not-boring math to measure code’s ... by dooglius on Friday August 02, 2019 @09:54AM (#20592898)
That 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.
[ Parent | on HN ]