Data Structures with Generic Types in Java/

...

/

Amortized Analysis of Spreading and Gathering

Amortized Analysis of Spreading and Gathering

Learn about the analysis of gather and spread methods.

We'll cover the following...

Next, we consider the cost of the gather(u) and spread(u) methods that may be executed by the add(i, x) and remove(i) methods. Let’s have a look at them:

Press + to interact
void spread(Node u) {
  Node w = u;
  for (int j = 0; j < b; j++) {
    w = w.next;
  }
  w = addBefore(w);
  while (w != u) {
    while (w.d.size() < b)
      w.d.add(0, w.prev.d.remove(w.prev.d.size() - 1));
    w = w.prev;
  }
}

The implementation of the gather() method is as follows:

Press + to interact
void gather(Node u) {
  Node w = u;
  for (int j = 0; j < b - 1; j++) {
    while (w.d.size() < b)
      w.d.add(w.next.d.remove(0));
    w = w.next;
  }
  remove(w);
}

Amortization

The running time of each of these methods is dominated by the two nested loops. Both the inner and outer loops execute at most b+1b + 1 times, so the total running time of each of these methods is O((b+1)2)=O(b2)O((b + 1)^2) = O(b^2). However, the following lemma shows that these methods execute on at most one out of every bb calls to add(i, x) or remove(i).

Lemma: If an empty SEList is created and any sequence of m≥1m \ge 1 calls to add(i, x) and remove(i) is performed, then the total time spent during all calls to spread() and gather() is O(bm)O(bm).

Proof: We will use the potential method of amortized analysis. We say that a node u is fragile if u’s block does not contain bb elements (so that u is either the last node, or contains ...