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

[Peter Alexander]

On Wednesday, 19 February 2014 at 09:46:04 UTC, Gopan wrote:
> On Wednesday, 19 February 2014 at 09:09:25 UTC, Tobias Pankrath
>> 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.
>
> I agree that vals.length is known at compile time.  But while 
> running the application, it iterates through every val in the 
> input list until a match is found.
> So, how can that be considered O(1)?
>
> ...
>
> Or, is my undertanding about Big-O notation of complexity wrong?

Your understanding is probably fine. It's just one of those 
technicalities which is a bit misleading.

The algorithm is O(vals.length), there's no arguing about that, 
but since vals.length is a constant, it's also O(1) because O(1) 
= O(2) = O(1,000,000) = O(k) for any constant k.

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.