Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in C++

Amortized Analysis of Spreading and Gathering

Explore the amortized cost of the spread and gather operations in SEList, a linked list variant. Understand how these methods impact the performance of add and remove operations, and learn to analyze their efficiency using the potential method in amortized analysis.

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. For the sake of completeness, here they are:

C++
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;
  }
}
...
C++
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 ...