4 ms·
I will nitpick your nitpick. In a language with arbitrary size integers you're right. This is a C++ int, therefore 32/64 bits (in all sane cases, ik the spec do
by 8192kjshad09- 5y ago
I will nitpick your nitpick. In a language with arbitrary size integers you're right. This is a C++ int, therefore 32/64 bits (in all sane cases, ik the spec doesn't specify), so the maximum number of cycles is upper bounded. Therefore modulo on C++ ints is is O(1).
- jagrsw 5y agoBut having an upper bound doesn't make it O(1) automatically, no? It'd be like saying that Erastotenes' sieve is O(1) b/c for 64bit integers we know what upper exec time limit is? IMO id'd be rather creative use of current conventions around comp. complexity, but my knowledge of those topics is bad.
- laszlokorte 5y agobig O() notation is simply not precise enough (and not meant to be) to be used in such nitpicky discussions. Everything is O(1) for a large anough constant, for example O(live time of the universe). There are other notations like small o(), Omega(), omega() or theta() to capture the asymtotic runtime behavior more or less precisely.