Warp schrieb:
> Darren New <dne### [at] sanrrcom> wrote:
>> http://doc.trolltech.com/4.2/containers.html#algorithmic-complexity
> 
>   Everybody always says that "inserting in the middle of a linked list is
> a constant-time operation". My response to that is: "Ok, if that is so, then
> give me a function which takes a linked list and an element as parameters,
> and make the function insert the element in the exact middle of the list in
> constant time. I'll wait."
> 
>   The claim is rather imprecise. You can't just magically insert an element
> in the middle of a list in constant time. You have to get there somehow first.
> Only if you happen to have, from some previous operation, an iterator pointing
> to the place where you want to insert, *then* it will be a constant-time
> operation.

The claim /is/ precise: Whenever you want to insert an element into 
/any/ data structure, you /always/ need to first figure out /where/ to 
insert, so the cost of an insertion operation is /always/ specified 
presuming that the insertion is to happen at a /predetermined/ location.

Of course if someone only considers the cost of insertion, neglecting 
any other costs his algorithm may incur, he's doin' it wrong...

Post a reply to this message