Time complexity of append operation in simple array

Question

In the worst case while appending an element(inserting at end) array can be full. So a new array is created and n elements are copied from this array to the new array.

I read in literature that worst case time complexity of this operation is O(1), why so? shouldn't it be O(n)?

I did read this question. But did not make any sense to me!

Answer 1

The operation itself is O(n).

If you get the average operations per element, you get O(1), this is the amortized cost.

See more at http://en.wikipedia.org/wiki/Amortized_analysis

Answer 2

I see it the same way that you do.

If it was a List, then it was O(1) to add an element at the end.

But in the case of an array, if it´s full you need to create a new one, copy all the elements in the old array, and then add the new element.

For me it´s O(n) too.

Answer 3

In case of static list/array the time complexity must be O(n), but in case of dynamic array/list, the time complexity comes O(1) because in dynamic array there is a facility to allocate extra memory for the append operation .