Data Structures, Algorithms, & Applications in Java
Amortized Complexity
Copyright 1999 Sartaj Sahni

1. Since the worst-case step count for an insert operation is 2n+4, sum0 <= i <= 4(2i+4) = 4 + 6 + 8 + 10 + 12 = 40 is an upper bound on the step count for the sequence of 5 inserts.
2. The maximum number of elements already in the array at the time an insert operation begins is 4. Therefore, the worst-case step count of an insert operation is 2*4+4 = 12. Therefore, 5*12 = 60 is an upper bound on the step count for the sequence of 5 inserts.

1. Aggregate Method
   In the aggregate method, we determine an upper bound UpperBoundOnSumOfActualCosts(n) for the sum of the actual costs of the n operations. The amortized cost of each operation is set equal to UpperBoundOnSumOfActualCosts(n)/n. You may verify that this assignment of amortized costs satisfies Equation (1) and is, therefore, valid.
   
   
2. Accounting Method
   In this method, we assign amortized costs to the operations (probably by guessing what assignment will work), compute the P(i)s using Equation (2), and show that P(n)-P(0) >= 0.
   
   
3. Potential Method
   Here, we start with a potential function (probably obtained using good guess work) that satisfies Equation (3), and compute the amortized complexities using Equation (2).

month          |  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
actual cost    | 50  50 100  50  50 100  50  50 100  50  50 200  50  50 100  50
amortized cost | 75  75  75  75  75  75  75  75  75  75  75  75  75  75  75  75
P()            | 25  50  25  50  75  50  75 100  75 100 125   0  25  50  25  50

widget        |    1    2    3    4    5    6    7    8    9   10   11   12   13   14 
actual cost   |    1    1    1    1    1    1    1    1    1    2    1    1    1    1
amortized cost| 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12
P()           | 0.12 0.24 0.36 0.48 0.60 0.72 0.84 0.96 1.08 0.20 0.32 0.44 0.56 0.68
=============================================================================================
widget        |   15   16   17   18   19   20   21   22   23   24   25   26   27   28 
actual cost   |    1    1    1    1    1    2    1    1    1    1    1    1    1    1
amortized cost| 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12 1.12
P()           | 0.80 0.92 1.04 1.16 1.28 0.40 0.52 0.64 0.76 0.88 1.00 1.12 1.24 1.36

public class SubsetEnumerator
{
   // data member
   int n;      // set size
   int [] x;   // subset array
   
   /** constructor */
   public SubsetEnumerator(int theN)
   {
      n = theN;
      x = new int [n + 1];
   }

   /** @return next subset
     * @return null iff there is no next subset */
   public int [] nextSubset()
   {
      // generate next subset
      int i = n;
      while (i > 0 && x[i] == 1)
      {
         x[i] = 0;
         i--;
      }

      if (i == 0)
         return null;
      else
      {
         x[i] = 1;
         return x;
      }
   }

   /** test program */
   public static void main(String [] args)
   {
      int n = 4;
      int [] x;
      SubsetEnumerator sv = new SubsetEnumerator(n);

      // output all subsets other than the null subset
      while (true)
      {
         x = sv.nextSubset();
         if (x == null) break;
         for (int i = 1; i <= n; i++)
            System.out.print(x[i] + " ");
         System.out.println();
      }
   }
}

public class SimulatedSpace1
{
   // data members
   private int firstNode;
   SimulatedNode [] node;  // package visible

   // constructor
   public SimulatedSpace1(int numberOfNodes)
   {
      node = new SimulatedNode [numberOfNodes];

      // create nodes and link into a chain
      for (int i = 0; i < numberOfNodes - 1; i++)
         node[i] = new SimulatedNode(i + 1);
      // last node of array and chain
      node[numberOfNodes - 1] = new SimulatedNode(-1);
      // firstNode has the default initial value 0
   }
   
   public int allocateNode(Object element, int next)
   {// Allocate a free node and set its fields.
      if (firstNode == -1)
      {   // double number of nodes
          node = (SimulatedNode []) ChangeArraySize.
                 changeSize1D(node, 2 * node.length);
          // create and link new nodes
          for (int i = node.length / 2;
               i < node.length - 1; i++)
             node[i] = new SimulatedNode(i + 1);
          node[node.length] = new SimulatedNode(-1);
          firstNode = node.length / 2;
      }

      int i = firstNode;         // allocate first node
      firstNode = node[i].next;  // firstNode points to
                                 // next free node
      node[i].element = element; 
      node[i].next = next;
      return i;
   }
   
   public void deallocateNode(int i)
   {// Free node i.
      // make i first node on free space list
      node[i].next = firstNode;
      // remove element reference so that space can be garbage collected
      node[i].element = null;
      firstNode = i;
   }
}

1. The element in each set that has never been moved has 0 credits.
2. The credits on an element that has moved at least once is at least L - (number of times this element has moved).

/** rearrange railroad cars beginning with the initial order
 * inputOrder[1:theNumberOfCars]
 * @return true if successful, false if impossible. */
public static boolean railroad(int [] inputOrder,
                      int theNumberOfCars, int theNumberOfTracks)
{
   // code of complexity O(numberOfTracks) comes here

   // rearrange cars
   for (int i = 1; i <= numberOfCars; i++)
      if (inputOrder[i] == nextCarToOutput)
      {// send car inputOrder[i] straight out
          System.out.println("Move car " + inputOrder[i] + " from input "
                             + "track to output track");
          nextCarToOutput++;
 
          // output from holding tracks
          while (smallestCar == nextCarToOutput)
          {
             outputFromHoldingTrack();
             nextCarToOutput++;
          }
      }
      else
         // put car inputOrder[i] in a holding track
         if (!putInHoldingTrack(inputOrder[i]))
            return false;

   return true;
}

1. What is the relationship between a correct assignment of amortized complexities to operations and the actual complexities of these operations?
2. How are potential function, amortized complexity, and actual complexity related?
3. The McWidget company has been bought out by a computer manufacturer who insists that all displays be in binary. Rework the McWidget example using a binary display.
4. Suppose that a sequence of tasks is performed. The actual complexity of the ith task is 1 when i is not a power of 2. When i is a power of 2, the complexity of the ith task is i. Use each of the methods (a) aggregate, (b) accounting, and (c) potential function to show that the amortized complexity of a task is O(1).
5. Imagine that a data structure is represented as an array whose initial length is 1. The data structure operations are insert and remove. An insert takes 1 time unit except when the number of elements in the data structure prior to the insert equals the array length n; at this time, the insert takes n time units because we double the array length. A remove takes 1 time unit except when the number of elements left in the array is less than (array length)/4. When the number of elements left in the array is less than (array length)/4, the array length is halved and the remove takes (array length)/2 time units. Use each of the methods (a) aggregate, (b) accounting, and (c) potential function to show that the amortized complexity of each data structure operation is O(1).