On Wednesday, 19 February 2014 at 22:05:49 UTC, Peter Alexander
wrote:
O(1) = O(2) = O(1,000,000) = O(k) for any constant k.
If you want to get even more anal about it, searching an array
is technically O(1) because an array cannot be bigger than
size_t.max, and since size_t.max is a constant, O(size_t.max)
is O(1). Again, completely misleading but technically correct
in an esoteric, academic way.
That's a useless oversimplification since for all sizes lesser
than size_t.max there is a better input-length depending bound
for the complexity. Just like every algorithm that is in O(n) is
also in O(n^3), but usually you are interested
• in the smallest upper bound
• that depends on the input.
The input dependency is important because it lets us reason about
how the algorithm might scale.
Now, let n be the size of input, for example in this application,
n is input.length.
--
int[] input = getInputFromSomeWhere();
foreach(i; input)
{
if(i.among!(1, 42, 12))
{
writeln(i);
break;
}
}
--
Now, among does not depend of input.length and it will never do
in any application. That is the sole reason I say it's O(1).
