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

[Gopan]

On Wednesday, 19 February 2014 at 19:45:39 UTC, Ali Çehreli wrote:
> On 02/19/2014 01:46 AM, Gopan wrote:
>
> > 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
Great !! Thank you Ali.  I am convinced.
You have just taught me my first lesson of CTFE.

After removing writeln() from the template, the following 
statements compiled without error, which means 'n' got computed 
at compile time.

const uint n = among(3, 1,2,5,3); //no error
int[n] arr; //no error.

And,
int v = 3;
const uint n = among(v, 1,2,5,3); //Error: variable v cannot be 
read at compile time
int[n] arr; Error: Integer constant expression expected instead 
of among(v, 1, 2, 5, 3)

My conclusion is that when both 'v' and 'vals' are known at 
compile time, the complexity is perfectly O(1).  I would even 
like to say O(0) at runtime :)
And, when either 'v' or 'vals' is not known at compile time, the 
complexity is O(vals.length) because the computation happens at 
runtime.

> [1] http://ddili.org/ders/d.en/tuples.html
I have already started learning your tutorial.  It is great !!

Thanks all who posted.  I learnt from every post.  I love this 
forum.