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
