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.
