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

[Tobias Pankrath]

On Wednesday, 19 February 2014 at 13:11:32 UTC, Dicebot wrote:
> On Wednesday, 19 February 2014 at 13:03:38 UTC, Tobias Pankrath 
> wrote:
>> On Wednesday, 19 February 2014 at 09:46:04 UTC, Gopan wrote:
>>> Index of 3 in (1,2,5,3) is 4
>>>
>>> Or, is my undertanding about Big-O notation of complexity 
>>> wrong?
>>>
>>> Thanks,
>>> Gopan
>>
>> O(1) = O(k) for any constant k.
>
> I don't think it is legit to speak about k as constant here. It 
> is constant for any specific function instance but not for 
> template meta-algorithm as a whole.

Yep, the meta-algorithm is O(n) but the specific instance used in 
the program is O(k).

We need to agree on a) what the variables mean and on b) the 
artifact whose complexity is of interest.