News for hackers. Stuff that matters.
Re:Big O Notation – Using not-boring math to measure code’s ... by concert-gilled on Friday August 02, 2019 @09:11AM (#20592645)
> This is not the reason we ignore multiplicative constants in complexity analysis.

What is the reason?

Re:Big O Notation – Using not-boring math to measure code’s ... by rand_r on Friday August 02, 2019 @10:05AM (#20592988)
One part is that Big-O is an upper bound that kicks in for sufficiently large n.

For example, a O(log(n)) function will be faster than a O(k * n) function, for any fixed k, when n>j (for some fixed j i.e. when n is large enough). When comparing major classes of functions (n, log(n), 2^n, etc,), constant multiples don't matter, mathematically.

The other reason is that when comparing two functions with a similar amount of constant steps, let's say 5n vs 2n, it's impossible to say which is faster in the real world, so it's simpler and just as useful to collapse the set of O(k * f(n)) functions into O(f(n)).

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.

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.