Amortized Cost

Today I continued with the analysis of ArrayStacks, in particular Lemma 2..1. here is an alternate presentation of amortized analysis.

We use Lemma 2..1 as follows. The goal of analyzing running time is to estimate the execution of the entire program, say a program which used ArrayStacks. When doing that, we will have to add up the cost of all the calls to the ArrayStack operations over the whole program. The difficulty is that when doing so, we would have to be very careful about adding the cost of add and remove since they differ depending on the size. So instead, we take the following approach:

• First, we pretend that there exist coins or tokens that say "O(1) free unit of computation".
• We now make up some system of each data structure method creates or spends coins. It is important to remember that the actual code is not changing, these coins are just part of our analysis.
  • In the ArrayStack, each add and remove operation will create one coin and give it to the ArrayStack.
  • If the ArrayStack has size \(n\), the resize operation will spend \(n\) coins.
• We say the amortized cost of a data structure operation is actual cost + coins created - coins spent. Note that the amortized cost depends on our choice of coins and so a single data structure could have multiple amortized costs.
  • The resize operation has amortized cost \(O(1)\), since it has actual cost \(O(n)\) but we spend \(n\) coins, each allowing us to do \(O(1)\) work for "free".
  • The add and remove operations have amortized cost \(O(n-i)\). They have their actual cost without resize, which is \(O(n - i)\). They have the amortized cost of resize which is \(O(1)\). And then they have to create one coin, which costs \(O(1)\) work to create the coin. So in total, \(O(n-i)\).
• Next, we verify that we always have more coins than we spent. This is exactly Lemma 2..1 since Lemma 2..1 says we deposit more coins than we spend.

The result is the following statement:

In a program which makes calls to an ArrayStack, adding up the actual cost of all data structure
operations is equal to adding up all the stated amortized costs for all operations.

The reason for the above statement is that we "paid" computation to create a coin and later spent it so in the total sum over all operations, we get the same result. The point of doing this is that it is easier to add up the amortized costs, since the amortized cost of add and remove is always \(O(n-i)\).

Exercises

• Exercise 2..1 only for ArrayStack. Use big-O to discuss why an add_all operation which makes repeated calls to add is not efficient on an ArrayStack. Write pseudocode for a more efficient add_all operation, and give its new big-O execution time.

• After looking at various options for C++ and how it will fit into this course, I think "Thinking in C++" will work well. Our goal is not to learn C++ (since it is a very big language with many features), but to just learn enough of C++ to see the ideas in the course. Thinking in C++ volume 1 can be downloaded here.
  • Chapter 1 is just concepts of classes which we covered in mcs260 and mcs275 so should all be familiar, you can just skim it.
  • Chapter 2: some basics of compiling C++. In discussion this week, try and get through as many Exercises from Chapter 2 as you can. I will also talk about some of these concepts in lecture this week.