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
