Editing Amortized analysis (section)

===Dynamic array===
[[File:ArrayListAmotizedPush.png|thumb|right|270px|Amortized analysis of the push operation for a dynamic array]]
Consider a [[dynamic array]] that grows in size as more elements are added to it, such as {{code|ArrayList}} in Java or {{code|std::vector}} in C++.  If we started out with a dynamic array of size 4, we could push 4 elements onto it, and each operation would take [[constant time]].  Yet pushing a fifth element onto that array would take longer as the array would have to create a new array of double the current size (8), copy the old elements onto the new array, and then add the new element.  The next three push operations would similarly take constant time, and then the subsequent addition would require another slow doubling of the array size.

In general, for an arbitrary number <math>n</math> of pushes to an array of any initial size, the times for steps that double the array add in a [[geometric series]] to <math>O(n)</math>, while the constant times for each remaining push also add to <math>O(n)</math>. Therefore the average time per push operation is <math>O(n)/n = O(1)</math>. This reasoning can be formalized and generalized to more complicated data structures using amortized analysis.<ref name="Lecture 20" />