|
![](/i/fill.gif) |
clipka <ano### [at] anonymous org> wrote:
> Warp schrieb:
> > clipka <ano### [at] anonymous org> 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
|
![](/i/fill.gif) |