A dynamic array doubles its capacity whenever it becomes full. The amortised cost of one append operation is

Explanation

Copying happens at sizes 1, 2, 4, 8, ... so n appends cost about 2n element copies in total, i.e. O(1) per append on average.