On 2010-10-07 18:53:51 -0400, Andrei Alexandrescu
<seewebsiteforem...@erdani.org> said:
On 10/7/10 16:23 CDT, Michel Fortin wrote:
On 2010-10-07 14:38:50 -0400, Andrei Alexandrescu
<seewebsiteforem...@erdani.org> said:
At no point. "Linear" means "linear in the input size". I don't think
such arguments are valid.
It is linear in regard to the array length, the static array being the
input. That the length is known at compile time doesn't make it less of
an input for the "in" operator, even though it's not an input of the
program at runtime.
"Input" == "Input to the program" i.e. not known during compilation of
the program.
Sorry, but my interpretation in this context is that "Input" should be
"Input to the 'in' operator". Sure, it won't affect the complexity of
the program if the input of the operator is constant, but the
complexity of that operator is still linear in the sense that the time
it takes for one search scales linearly with the size of the input.
That the size of the input is decided at runtime or at compile time
does not change the complexity of the operator, nor does it make it
less stupid to use the operator on arrays longer than a few elements.
"in" shouldn't be allowed to perform a linear operation, and I mean
linear relative to the size of it's input.
--
Michel Fortin
michel.for...@michelf.com
http://michelf.com/
