Search code examples
arrayscomputer-sciencetime-complexity

Time complexity of append operation in simple array

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!

Solution

  • 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