Why function template 'among' is of complexity O(1) and not O(n)?

[Chris Williams]

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.