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

Gopan gggopan at gmail.com
Wed Feb 19 01:46:03 PST 2014


On Wednesday, 19 February 2014 at 09:09:25 UTC, Tobias Pankrath 
wrote:
> 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.

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)?

See my test app and output.

uint among(T, Us...)(T v, Us vals)
{
     foreach (i, U; Us)
     {
	writeln("checking ", v, " == ", vals[i]);
         if (v == vals[i])
	    return i + 1;
     }
     return 0;
}

void main()
{
     uint index = among(3, 1,2,5,3);
     writeln("Index of 3 in (1,2,5,3) is ", index);
}

outrput of running the app:
checking 3 == 1
checking 3 == 2
checking 3 == 5
checking 3 == 3
Index of 3 in (1,2,5,3) is 4

Or, is my undertanding about Big-O notation of complexity wrong?

Thanks,
Gopan


More information about the Digitalmars-d-learn mailing list