On Wednesday, 19 February 2014 at 22:05:49 UTC, Peter Alexander
wrote:
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 basically saying that on any linear bouded automaton, all
algorithms (except an infinite loop) are O(1) - which is silly.
To the OP:
The among() function is defined to template out into multiple
versions of itself depending on the number of arguments, rather
than using variadic parameter checking during runtime.
When the template writes out the definition of the function, if
the parameters can be interpreted during compile-time, then the
foreach ( O(n) ) will be run by the compiler to detect the
correct parameter and the function will be written out as just as
a return statement in the body, without the loop. So during
runtime, the function would have an O(1) runtime. If the
parameters can't be determined during compile-time then the
function will be written out with the contents of the foreach
copied into the body as many times as there are parameters,
making the runtime O(n), where n is the number of parameters to
the function.
Where people are getting a bit technical is that, because the
function is generated by a template the following two calls:
among("a", "b", "c");
among("a", "b", "c", "d");
end up declaring two separate functions, one which accepts three
parameters and the other which accepts four. The version which
accepts three parameters will always run the same speed no matter
what you call it - since it does the same thing exactly three
times. The version which accepts four parameters is the same.
Since they don't have any logic - they just run through a
constant list of operations with no loop - one can say that they
are O(1). Technically, it's true, but also a mildly pointless
distinction to make.
