3 ms·

Effectively constant seems like a reasonable thing to say if the real world number of operations is upper bounded by six. I don't interpret that claim as makin

Effectively constant seems like a reasonable thing to say if the real world number of operations is upper bounded by six. I don't interpret that claim as making any claim about the theoretical asymptotic complexity of an algorithm. Of course, as the author notes near the end, this also means that any real world algorithm running on a real world data type which is bounded in size can also be considered "effectively constant", which does throw doubt onto the effectiveness of the term. I guess in the real world we should use graphs in units of time instead of classes of functions to discuss performance based on input size, since that's what we care about. Also interesting to note is that"effectively constant", although extremely hand-wavy and not rigorous, is used even by computer scientists to denote extremely slow growing functions. A professor once used similar words to describe the complexity of the inverse Ackerman function: https://en.m.wikipedia.org/wiki/Ackermann_function#Inverse https://en.m.wikipedia.org/wiki/Ackermann_function#Inverse

jerf 9y ago
"Of course, as the author notes near the end, this also means that any real world algorithm running on a real world data type which is bounded in size can also be considered "effectively constant", which does throw doubt onto the effectiveness of the term." 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.
- kbenson 9y ago
  > 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?
victor___ 9y ago
I don't think pulling out the number 6 separately from the constant factor results in an apples-to-apples comparison with other operations with logarithmic complexity. The 32-way tree operations have asymptomic complexity 6 * C_1 * log(n) = C_2 * log(n) Operations on a balanced binary tree have asymptotic complexity C_3 * log(n) = 6 * C_4 * log(n). The only difference between the two data structures is the actual values of the constants. I think the Scala people have a valid point that logarithmic complexity may be as good (or nearly as good) as constant-time in practice. The precise way the claim is formulated is wrong and abuses big-O analysis. A more correct argument is to choose a practical upper bound on log(n). E.g. maybe 64. Then multiply that by the constant factor (not playing any tricks with splitting out 6 *). If that number is always good enough if practice, then you don't need to worry about your operation being logarithmic.
- deleted 9y ago
  [deleted]
- rrobukef 9y ago
  I don't think they should use effectively constant. Because the difference between O(1) and O(log(n)) may not be very big but the difference between O(n) and O(n log(n)) is very measurable. Even for small n.
nwellnhof 9y ago
> Also interesting to note is that"effectively constant", although extremely hand-wavy and not rigorous, is used even by computer scientists to denote extremely slow growing functions. Another example is Donald Knuth who claims in TAOCP, section 4.3.3 "How fast can we multiply", that multiplication algorithms are effectively linear. Quote: "For all practical purposes we can assume that [...] the Schönhage-Strassen multiplication technique will have a running time linearly proportional to n. [...] The practical problem of fast multiplication is therefore solved, except for improvements in the constant factor." This really stuck out to me.

jerf 9y ago

"Of course, as the author notes near the end, this also means that any real world algorithm running on a real world data type which is bounded in size can also be considered "effectively constant", which does throw doubt onto the effectiveness of the term." 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.

kbenson 9y ago
> 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?

victor___ 9y ago

I don't think pulling out the number 6 separately from the constant factor results in an apples-to-apples comparison with other operations with logarithmic complexity. The 32-way tree operations have asymptomic complexity 6 * C_1 * log(n) = C_2 * log(n) Operations on a balanced binary tree have asymptotic complexity C_3 * log(n) = 6 * C_4 * log(n). The only difference between the two data structures is the actual values of the constants. I think the Scala people have a valid point that logarithmic complexity may be as good (or nearly as good) as constant-time in practice. The precise way the claim is formulated is wrong and abuses big-O analysis. A more correct argument is to choose a practical upper bound on log(n). E.g. maybe 64. Then multiply that by the constant factor (not playing any tricks with splitting out 6 *). If that number is always good enough if practice, then you don't need to worry about your operation being logarithmic.

deleted 9y ago
[deleted]
rrobukef 9y ago
I don't think they should use effectively constant. Because the difference between O(1) and O(log(n)) may not be very big but the difference between O(n) and O(n log(n)) is very measurable. Even for small n.

nwellnhof 9y ago

> Also interesting to note is that"effectively constant", although extremely hand-wavy and not rigorous, is used even by computer scientists to denote extremely slow growing functions. Another example is Donald Knuth who claims in TAOCP, section 4.3.3 "How fast can we multiply", that multiplication algorithms are effectively linear. Quote: "For all practical purposes we can assume that [...] the Schönhage-Strassen multiplication technique will have a running time linearly proportional to n. [...] The practical problem of fast multiplication is therefore solved, except for improvements in the constant factor." This really stuck out to me.