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

[anonymous]

On Thursday, 20 February 2014 at 09:42:34 UTC, Gopan wrote:
> const uint n = among(3, 1,2,5,3); //no error
> int[n] arr; //no error.
>
> And,
> int v = 3;
> const uint n = among(v, 1,2,5,3); //Error: variable v cannot be 
> read at compile time
> int[n] arr; Error: Integer constant expression expected instead 
> of among(v, 1, 2, 5, 3)
>
> My conclusion is that when both 'v' and 'vals' are known at 
> compile time, the complexity is perfectly O(1).  I would even 
> like to say O(0) at runtime :)
> And, when either 'v' or 'vals' is not known at compile time, 
> the complexity is O(vals.length) because the computation 
> happens at runtime.

When v and vals are known at compile time, that opens up the
possibility of CTFE. It's necessary but not sufficient. When a
value is needed at compile time (e.g. initializer for a static
variable, length of a static array), then CTFE is forced. When
the value is not needed at compile time, the optimizer may go for
it, but that's not guaranteed.