4 ms·
O(n) isEven function compared to the obvious constant time O(1) modulo algorithm In the holy name of nitpickiness: the modulo operation is not always O(1), as
by jagrsw 5y ago
O(n) isEven function compared to the obvious constant time O(1) modulo algorithm
In the holy name of nitpickiness: the modulo operation is not always O(1), as div/mod CPU instructions have complex internal implementations and require varying number of cycles depending on what the input args are.
However, for x%2 it'll be probably O(1), both on the cpu level, and b/c it'll get optimized to something like x&1 by most compilers (at least for unsigned values)
- 8192kjshad09- 5y agoI 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.
- athrowaway3z 5y agoIt states "constant time O(1) modulo _algorithm_" for implementing an isEven function.