I think part of the problem is signaling. I get annoyed when I see people saying “X is true modulo Y”, because that seems like an inflationary use of the word “modulo”. But if somebody uses “modulo” that makes them sound smart, because they are using math jargon!
Anyway, I try to avoid using technical terms I don’t feel I have a firm grasp on, and calibrate the fuzziness of my language to the fuzziness of my thinking.
I’ve always felt that this is actually a defect in big O notation. If we want to know how long a computation is going to take, it honestly doesn’t help us at all to know that it’s O(1), because as you point out it could be a constant time so mind-bendingly huge that it will never complete. The O(n) or even O(2^n) method might well be faster in realistic situations.
Seems like we actually should be measuring our computations some other way, perhaps in terms of the actual number of seconds (or if you want to be cross-platform, number of steps) involved. So you wouldn’t say O(1), you’d say “1200 steps”; you wouldn’t say O(n), you’d say “480n steps”.
I think part of the problem is signaling. I get annoyed when I see people saying “X is true modulo Y”, because that seems like an inflationary use of the word “modulo”. But if somebody uses “modulo” that makes them sound smart, because they are using math jargon!
Anyway, I try to avoid using technical terms I don’t feel I have a firm grasp on, and calibrate the fuzziness of my language to the fuzziness of my thinking.
I think that this use of “modulo” is close enough to the mathematical reason to allow.
Likewise, “f(x) is O(g(x))” only means that f(x)/g(x) is bounded, not that the bound is small. In particular, O(3^^^3) means the same thing as O(1).
I’ve always felt that this is actually a defect in big O notation. If we want to know how long a computation is going to take, it honestly doesn’t help us at all to know that it’s O(1), because as you point out it could be a constant time so mind-bendingly huge that it will never complete. The O(n) or even O(2^n) method might well be faster in realistic situations.
Seems like we actually should be measuring our computations some other way, perhaps in terms of the actual number of seconds (or if you want to be cross-platform, number of steps) involved. So you wouldn’t say O(1), you’d say “1200 steps”; you wouldn’t say O(n), you’d say “480n steps”.