News for hackers. Stuff that matters.
Re:Big O Notation – Using not-boring math to measure code’s ... by falcor84 on Friday August 02, 2019 @08:51AM (#20592554)
> As n gets really big, adding 100 or dividing by 2 has a decreasingly significant effect.

I was annoyed to see that comment about division, as of course dividing n by 2 has exactly the same effect regardless of the size of n. This is not the reason we ignore multiplicative constants in complexity analysis.

It reminded me of the joke that Earth's circumference is pretty much the same as its diameter, since the the size of pi is negligible at that scale.

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.