undefined | Better HN

0 pointsdbaupp8y ago0 comments

What exactly are you nitpicking?

1000^depth is not a constant: the function here is "f(depth) = number of times the inner loop body executes". f(depth) = O(1000^depth).

And, "times" here is serving the same role as "comparisons" in "Mergesort takes O(n log n) comparisons": it's referring to the thing that f is actually counting.

0 comments

colanderman8y ago

Given O(f(x)), x is almost always understood to be measurement of the work input to the algorithm. Loop nesting depth is not a measurement of work input, it's a property of the code – "1000^depth" is constant for any given algorithm.

Yes, O(…) is just a mathematical construct, so you can apply it the way you have to mean "the amount of work done for a given input size increases exponentially with respect to the number of nested loops iterating over the input"… but that's not how most people interpret it in the context of a computer algorithm. (The exception would be if the nesting depth were dynamically determined by an input parameter, but I don't think that's what anyone here is talking about.)

Anyway I'm not trying to argue, I agree with your point, but I think everyone here is talking past each other trying to say the same thing, ultimately due to imprecision in semantics.

dbauppOP8y ago

The only difference between what is "code" and what is "work" is context: in this case, the work of interest is a property of some input code. If you want a framing that matches your notions of input better, just imagine we're measuring the asymptotics of a VM/interpreter, and then the code truly is the input.

j / k navigate · click thread line to collapse