"in" everywhere

[Michel Fortin]

On 2010-10-07 18:53:51 -0400, Andrei Alexandrescu 
<SeeWebsiteForEmail at erdani.org> said:

> On 10/7/10 16:23 CDT, Michel Fortin wrote:
>> On 2010-10-07 14:38:50 -0400, Andrei Alexandrescu
>> <SeeWebsiteForEmail at 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.fortin at michelf.com
http://michelf.com/