Re:Scala Vector operations aren't “Effectively Constant” time
by kbenson on Wednesday August 09, 2017 @02:25PM
(#14972153)
> In another example, 1 nanosecond and 1 millisecond, separated by six orders of magnitude, are both effectively instant to a human... at least, as long as it's only happening once. Start looping on that and the differences rapidly become, ah, effective.
Well, yeah. Looping on some operation changes the complexity to n*(O(interion operation)). That changes the complexity of O(log(n)) to O(n·log(n)).
Also, anyone that's actually learned anything about time complexity analysis and order of magnitude notation will know that the constants which aren't shown can and often do swamp the other factors in practice, depending on the algorithm.
Finally, I think it's totally acceptable to take these analysis out of the theoretical realm of math and apply them to real world limits. If there's a hard limit for n such that it's not infinite, why not use that as an upper bound constant where applicable?
They're not all effectively constant though. I can say that effectively all web pages render within 100 seconds and thus web page rendering is O(1), but it's not true because "between visually instantaneous and 100 seconds" is not effectively constant.
In another example, 1 nanosecond and 1 millisecond, separated by six orders of magnitude, are both effectively instant to a human... at least, as long as it's only happening once. Start looping on that and the differences rapidly become, ah, effective.
The root problem here is that pragmatic measures don't fit in math and math doesn't fit in pragmatic measures, and you need to at least be careful not to equivocate back and forth. But there's nothing wrong with either one; you just need to know where you stand. You can't help it anyhow; we are not capable of dealing with the universe with mathematical precision everywhere, we lack the computational power to do so, assuming it is even theoretically possible.