8< ----- snip -----

> I don't know how Array is implemented.. I think matz (Ruby's author) has
> chosen a datastructure with constant-time head/tail insert/removal.
> Not sure though.
> 
> It would be nice with an O(x) chart of the most common operations:
> 
> my guess .. please correct me if im wrong
> 
> -------------------------------
> push element         O(1)
> pop element          O(1)
> shift element        O(?)     I hope O(1)
> unshift element      O(?)     I hope O(1)
> insert element       O(n)
> remove element       O(n)
> ...
> 
> --
> Simon Strandgaard
> 
> 

Assuming that the Array is set up like a C/C++ (double) linked list
with pointers, then all should take Theta(1), except insert which can
take Theta(n) if the element is out of the Array boundary and all
intermediate items need to be created first. If insert/remove
specifies inserting elements into a sorted list then it can be done in
Theta(log n) by using a binary search to find the location to insert.