clipka <ano### [at] anonymousorg> wrote:
> Warp schrieb:
> > clipka <ano### [at] anonymousorg> wrote:
> >> 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.
> > 
> >   "Inserting" and "inserting in the middle" are two slightly different
> > things. The latter is making a more concrete claim.
> > 
> >   As said, if you really can "insert in the middle" of a linked list in
> > constant time, give me such a function.

> It's not "in the middle" in the sense of "at the centroid", but in the 
> sense of "not at the beginning nor at the end, but at an arbitrary 
> position somewhere in between".

  Which is O(n) because you have to get there first.

-- 
                                                          - Warp

Post a reply to this message