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

[Tobias Pankrath]

On Wednesday, 19 February 2014 at 08:58:10 UTC, Gopan wrote:
> Recently, I came across the following thread
> http://forum.dlang.org/thread/l8nocr$1dv5$1@digitalmars.com?page=2
>
> On Monday, 16 December 2013 at 22:10:52 UTC, Andrei 
> Alexandrescu wrote:
>> On 12/16/13 1:45 PM, Walter Bright wrote:
>>> On 12/16/2013 12:38 PM, Andrei Alexandrescu wrote:
>>>> uint among(T, Us...)(T v, Us vals)
>>>> {
>>>>    foreach (i, U; Us)
>>>>    {
>>>>        if (v == vals[i]) return i + 1;
>>>>    }
>>>>    return 0;
>>>> }
>>>
>>> This has O(n) behavior, which might be unexpected for the 
>>> user.
>>
>> It's O(1) because the data size is in the source text. There's 
>> no variable n.
>
> To me, it looks like a Linear Search and hence of complexity 
> O(n).
> Could somebody please elaborate why it is O(1) and not O(n)?
> If there is an article/document that I am to read to understand 
> this, please cite it.
>
> (I am a beginner level programmer and new to D Language.)
>
> Thanks,
> Gopan.

It's O(k) with k = vals.length, which is the number of arguments 
given to the function, which is a compile time constant and not 
dependent on any input of the final program. In O(n) the n always 
relates to the input somehow.