Amortized analysis

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 ArrayList in Java or 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 if we consider an arbitrary number of pushes n + 1 to an array of size n, we notice that push operations take constant time except for the last one which takes ${\displaystyle \Theta (n)}$ time to perform the size doubling operation. Since there were n + 1 operations total we can take the average of this and find that pushing elements onto the dynamic array takes: ${\displaystyle {\tfrac {n\Theta (1)+\Theta (n)}{n+1}}=\Theta (1)}$, constant time.[3]

Shown is a Python3 implementation of a Queue, a FIFO data structure:

# Define a class named Queue
class Queue:
  # Define the constructor method that initializes two empty lists
  def __init__(self):
    self.input = [] # This list will store the elements that are enqueued
    self.output = [] # This list will store the elements that are dequeued

  # Define a method named enqueue that takes an element as a parameter
  def enqueue(self, element):
    self.input.append(element) # Append the element to the input list

  # Define a method named dequeue that returns the first element that was enqueued
  def dequeue(self):
    if not self.output: # If the output list is empty
      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

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 ${\displaystyle 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 ${\displaystyle O(n)}$ time, which implies that the amortized time of each dequeue operation is ${\displaystyle O(1)}$.[4]

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 ${\displaystyle O(1)}$.