Editing Dynamic array (section)

== Geometric expansion and amortized cost ==

To avoid incurring the cost of resizing many times, dynamic arrays resize by a large amount, such as doubling in size, and use the reserved space for future expansion. The operation of adding an element to the end might work as follows:
<syntaxhighlight lang="c">
function insertEnd(dynarray a, element e)
    if (a.size == a.capacity)
        // resize a to twice its current capacity:
        a.capacity ← a.capacity * 2 
        // (copy the contents to the new memory location here)
    a[a.size] ← e
    a.size ← a.size + 1
</syntaxhighlight>
As ''n'' elements are inserted, the capacities form a [[geometric progression]]. Expanding the array by any constant proportion ''a'' ensures that inserting ''n'' elements takes [[Big O notation|''O''(''n'')]] time overall, meaning that each insertion takes [[Amortized analysis|amortized]] constant time. Many dynamic arrays also deallocate some of the underlying storage if its size drops below a certain threshold, such as 30% of the capacity. This threshold must be strictly smaller than 1/''a'' in order to provide [[hysteresis]] (provide a stable band to avoid repeatedly growing and shrinking) and support mixed sequences of insertions and removals with amortized constant cost.

Dynamic arrays are a common example when teaching [[amortized analysis]].<ref name="gt-ad"/><ref name="clrs"/>