Amortized Complexity - a Tool for Graph Algorithms (among others)

There are a lot of very cool problems in computer science that can be solved by using
an appropriate data structure; and the data structures are often easiest to describe in terms
of graphs. And of those data structures, one thing that often comes up is amortized algorithmic complexity. Amortized complexity is something which has been occupying my thoughts lately,
because it's come up in several real problems, so I'm in the mood to write about it, and it'll be
useful later.

The idea of amortized complexity is that for some structures, the worst case complexity
cost of a series of operations is different from the worst-case complexity of a single operation. In amortized complexity, you consider cases where some operation is inexpensive most of the time - but to keep it inexpensive most of the time, you need to periodically do something expensive.

As usual, the idea is clearer by example. Suppose you want to have a list of things. You want to be able to access any element by position quickly. You also want to be able to quickly add new things at the end of the list.

If you didn't want to be able to add things to the end of the list - that is, you knew the size of the list in advance - then it would be easy. You could just use an array, a sequence of values stored in adjacent memory locations. Then accessing an element by position is simple - just take the location of the beginning of the array, and add to it the position of the element you want. Updating is the same thing - just store things in the position. For example, in C, for a list of integers:

typedef int* int_list;

int_list create_list(int size) {
   return (int*) malloc(size*sizeof(int));
}

int get_from_list(int_list list, int position) {
   return *(list + position);
}

void set_in_list(int_list list, int position, int value) {
   *(list + position) = value;
}

But if you want to be able to extend the list, then you can't just use a simple array. An array gives you fixed length. So what do you do? You pull out the old classic hacking aphorism: "When all else fails, add indirection". Instead of using an array, you use a structure containing a pointer to an array,
and a length indicator. That way, you can replace the array with a longer one when you need to. Done
naively, you get something like:

typedef struct s_list {
   int length;
   int *array;
} *list;

list createList(int size) {
   list l = (l) malloc(sizeof(struct s_list));
   l.length = size;
   l.array = (int *)malloc(size * sizeof(int));
}

int get_from_list(list l, int pos) {
   return *(l->array + pos);
}

void add_to_list(list l, int val) {
   /* allocate a new array, and copy the old volues into it. */
   int *new_array = (int *)malloc((size + 1) * sizeof(int));
   for (int i=0; i < l->length; i++) {
      *(new_array + i) = *(l->array + i);
   }
   *(new_array + size) = val;
   /* replace the old array */
   l->array = new_array;
   l->length++;
}

Now, this obviously stinks. Every time you add an element to the list, you need
to copy the entire list. So adding an element to a list has complexity O(N) (where N is the size of the list); starting from an empty list and adding N elements is O(N²). That's not good.

The problem is, how can you do better? If you stop using an array, then you'll lose the
fast retrieval and update by position. If you keep using an array, and you don't know its
maximum size, you're stuck - you're eventually going to need to copy the array, and copying
the array is O(n) - so the worst case performance of adding to the array is O(n).

The trick is to consider a series of operations. Suppose that you use the following
trick:

• Keep the real length of the array, and the apparent length of the list separately;
• Each time you add an element, if the real length of the array is larger than
  the length of the list, add the value in an unused part of the array, and
  add one to the apparent length of the list.
• If you want to add an element, and the size of the array is the same as the size of the
  list, then re-allocate the array, making it double the size of the old array,
  and then copy the elements to the new array.

typedef struct s_elist {
   int list_length;
   int array_size;
   int *array;
} *elist;

void add_to_elist(elist el, int val) {
   if (el->list_length < el->array_size - 1) {
      *(el->array + el->list_length) = val;
      el->list_length++;
   } else {
      int new_size = el->array_size * 2;
      int *new_array = (int *)malloc(new_size * sizeof(int));
      for (int i=0; i < el->list_length; i++) {
         *(new_array + i) = *(el->array + i);
      }
      *(new_array + el->array_size) = val;
      el->array = new_array;
      el->list_length = new_size;
      el->list_length++;
   }
}

What's the complexity of that? Well, worst case is O(N), where N is the current size of the list. But suppose you actually added N elements to the list. The complexity is not
O(N²). It's just O(N). From the time you reallocate the array from size C to size 2×C,
you get to do C insertions with cost 1; and then you do one insert of cost C. So if you're looking at the performance of the series, you can amortize the cost over the operations, and say that
the amortized cost of each insert is 2; the amortized cost of C inserts is thus 2×C - that is, exactly the actual cost of C inserts.

There are two different ways of working out amortized costs: credit and debt based approaches.
In a credit based approach, you charge a cost to perform an expensive operation; and each time you do the cheap operation, you charge it extra time, earning some quantity of time as credit. If you can show that you'll never perform the expensive operation without having enough credit to
pay for it, then that cost you charged to the cheap operation is the amortized cost.

The credit based approach is similar - but you do the expensive operation first. So, if you don't owe
any time, you can perform the expensive operations. But when you do, you acquire a debt, and while you're
in debt, you can't perform the expensive operation. Each time you perform the cheap operation, you charge
it more than it actually costs to perform, and pay off part of the debt. If you can show that you never
need to perform the expensive operation while in debt, then the cost you assigned to the cheap operation
is the amortized cost.

Let's look at an example of pre-payment. We start with a list of size N, and start adding. Each
inexpensive operation really costs 1, but we'll charge it as 2. So each time we do a cheap add, we get 1
unit of credit. After N additions, we'll have accumulated N units of credit. Then we need to reallocate
the list - which costs N. So we're in the clear. The amortized cost of inserts is 2 - or O(1).