Array, AA Implementations

[Don]

Andrei Alexandrescu wrote:
> Bill Baxter wrote:
>> On Wed, Oct 21, 2009 at 6:35 PM, Andrei Alexandrescu
>> <SeeWebsiteForEmail at erdani.org> wrote:
>>
>>> 3. Remove some element from the container and give it to me
>>>
>>> E removeAny();
>>>
>>> 4. Add an element to the container is possible
>>>
>>> bool add(E);
>>
>>> I think any container must support these primitives in O(1), and I 
>>> find it
>>> difficult to think of a significant category of containers that can't
>>> support them (but then there may as well be, so please join me in 
>>> thinking
>>> of that). A lot of stuff can be done with only these few methods.
>>
>> I think balanced trees generally take O(lg N) to add and remove elements.
> 
> Good point, thanks. Logarithmic of better.
> 
> Andrei
Can it be amortized O(lg N) ?