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.

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.

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

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.

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.

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.

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

On Wednesday, 19 February 2014 at 19:45:39 UTC, Ali Çehreli wrote:
> ...

This is much better explanation - O(n) compile-time algorithm which results in O(1) run-time code generated :)

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;
> > }
[...]
> 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

Nope. v and vals are runtime parameters, their values are not
known at compile time. What's known at compile time is
vals.length.

On Wednesday, 19 February 2014 at 21:52:06 UTC, anonymous wrote:
> Nope. v and vals are runtime parameters, their values are not
> known at compile time. What's known at compile time is
> vals.length.

While this is correct, note that there is also an overload that takes `values` as compile-time parameters, generating a switch statement, which is especially interesting because the switch statement is a good opportunity for the compiler to optimise.