4

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!

Community
  • 1
  • 1
DDC
  • 834
  • 2
  • 9
  • 27

3 Answers3

4

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

Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176
  • 1
    I think this is the line at the heart: "The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost." – DDC Mar 04 '14 at 14:07
  • 1
    that's why exponential growth is used when resizing. – Karoly Horvath Mar 04 '14 at 14:08
  • Are you telling that when I will create new array it would exponentially larger than previous one? If so how to choose exponent values? – DDC Mar 04 '14 at 14:10
  • Is there any such rules? Can you point to some literature please? – DDC Mar 04 '14 at 14:13
  • first hit: http://stackoverflow.com/questions/1100311/what-is-the-ideal-growth-rate-for-a-dynamically-allocated-array – Karoly Horvath Mar 04 '14 at 14:14
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/48961/discussion-between-eddij-and-karoly-horvath) – DDC Mar 04 '14 at 14:16
0

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.

Oscar Bralo
  • 1,912
  • 13
  • 12
0

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 .

Prem Pratap Tiwari
  • 1