Editing Amortized analysis (section)

==Examples==
===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" />

===Queue===
Shown is a Python3 implementation of a [[Queue (abstract data type)|queue]], a [[FIFO (computing and electronics)|FIFO data structure]]:
<syntaxhighlight lang="python">
class Queue:
    # Initialize the queue with two empty lists
    def __init__(self):
        self.input = []  # Stores elements that are enqueued
        self.output = []  # Stores elements that are dequeued

    def enqueue(self, element):
        self.input.append(element)  # Append the element to the input list

    def dequeue(self):
        if not self.output:  # If the output list is empty
            # Transfer all elements from the input list to the output list, reversing the order
            while self.input:  # While the input list is not empty
                self.output.append(
                    self.input.pop()
                )  # Pop the last element from the input list and append it to the output list

        return self.output.pop()  # Pop and return the last element from the output list
</syntaxhighlight>

The enqueue operation just pushes an element onto the input array; this operation does not depend on the lengths of either input or output and therefore runs in constant time.

However the dequeue operation is more complicated.  If the output array already has some elements in it, then dequeue runs in constant time; otherwise, dequeue takes {{tmath|O(n)}} time to add all the elements onto the output array from the input array, where ''n'' is the current length of the input array.  After copying ''n'' elements from input, we can perform ''n'' dequeue operations, each taking constant time, before the output array is empty again. Thus, we can perform a sequence of ''n'' dequeue operations in only {{tmath|O(n)}} time, which implies that the amortized time of each dequeue operation is {{tmath|O(1)}}.<ref name=Grossman>{{cite web|last1=Grossman|first1=Dan|title=CSE332: Data Abstractions|url=http://courses.cs.washington.edu/courses/cse332/10sp/lectures/lecture21.pdf|website=cs.washington.edu|access-date=14 March 2015}}</ref>

Alternatively, we can charge the cost of copying any item from the input array to the output array to the earlier enqueue operation for that item.  This charging scheme doubles the amortized time for enqueue but reduces the amortized time for dequeue to {{tmath|O(1)}}.