Subj : Re: Looking for a nice data structure for lists...
To   : comp.programming
From : Googmeister
Date : Tue Oct 11 2005 06:22 am


Thad Smith wrote:
> DV wrote:
> > Is there a data structure for lists such that a list can be split in
> > half in constant time or its middle element found in constant time
> > (such as an array pointer + size variable) but also such that two lists
> > can be merged in constant time (such as a linked list)?  This isn't a
> > homework problem.
>
> Merging will take at least O(n).

I think you mean Omega(n). Big Oh notation is
not meaningful with lower bounds.

By "merging" I think the OP means concatenating (not
"merging" as in mergesort), so such a lower bound
does not apply anyway.

.