"in" everywhere

[Simen kjaeraas]

Stewart Gordon <smjg_1998 at yahoo.com> wrote:
>> Imagine, for instance, if we were to make Java's mistake of having List  
>> be an
>> interface which ArrayList and LinkedList implement and that List has a  
>> get()
>> function. Using ArrayList, get() has a complexity of O(1). Using  
>> LinkedList, it
>> has a complexity of O(n).
>
> Are you suggesting we just don't have a List interface, just to prevent  
> people from writing algorithms that work well in some list  
> implementations but poorly in others?  I'm not sure if that risk  
> outweighs any benefits....

Not at all. What is being argued is that an interface not only dictate
what the object does, but to an extent how it does it (i.e. complexity
guarantees).

Just as an interface offering only function signatures with no
explanation of what a particular function does, would be considered
insufficient or outright dangerous, as should one not warning of
complexity consideration.


>> To write efficient algorithms, you _must_ be able to rely on certain  
>> complexity
>> guarantees for the operations that you use. So, regardless of what those
>> complexity gurantees actually _are_, they need to be there.
>
> Setting the complexity guarantee of everything to O(n!) would achieve  
> _that_ aim in most everyday cases.... :)

As well as being completely useless.


-- 
Simen