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

[Ali Çehreli]

On 02/19/2014 01:46 AM, Gopan wrote:

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

You get that output only because you have inserted the writeln() 
expressions in there.

That foreach over variadic template arguments is a "compile-time 
foreach"[1]. For example, if v were 2 and vals were "1, 2, 3", the 
original code would be expanded to the following:

     if (2 == 1) return 1;    // i == 0
     if (2 == 2) return 2;    // i == 1
     if (2 == 3) return 3;    // i == 3

Since all of those conditions is known to be true or false at compile 
time, the compiler will reduce the code to the following:

     return 2;

Ali

[1] http://ddili.org/ders/d.en/tuples.html