Possible Duplicate:
A data structure supporting O(1) random access and worst-case O(1) append?
I saw an answer a while ago on StackOverflow regarding a provably optimal vector ("array list") data structure, which, if I remember correctly, lazily copied elements onto a larger vector so that it wouldn't cause a huge pause every time the vector reallocated.
I remember it needed O(sqrt(n)) extra space for bookkeeping, and that the answer linked to a published paper, but that's about it... I'm having a really hard time searching for it (you can imagine that searches like optimal vector are getting me nowhere).
Where can I find the paper?
I think that the paper you are referring to is "Resizable Arrays in Optimal Time and Space" by Brodnik et al. Their data structure uses the lazy copying dynamic array you mentioned in your question as a building block to assemble this structure. There is this older question on Stack Overflow describing the lazy-copying data structure, which might be useful to get a better feel for how it works.
Hope this helps!