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

Amortized Analysis of Spreading and Gathering

Explore the amortized analysis of spreading and gathering in linked lists, specifically within the SEList structure. Understand how these operations affect performance during add and remove methods, and learn how potential-based reasoning leads to efficient time complexity in Java implementations.

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:

Java
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 ...

Java
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 ...