I am still trying to improve the understanding of amortized analysis by students (as in a previous question). In many textbooks such as the CLRS, three methods are presented: aggregate, accounting, and potential. My question concerns the links and differences between accounting and potential method, and was actually inspired by questions from my students.

In the accounting method, one has to define a money cost for each operation, and show that at each step, the account contains enough money to pay for the actual cost of the operation. Otherwise stated, one needs to show that the account always has a nonnegative amount of money. To formally prove the nonnegativity of the account, a possibility that I like to present to my student is to relate the amount of money on the account with some quantity in the problem: For instance, for the amortized analysis of a binary counter, one can prove that the money on the account is always twice the number of 1 in the counter at each step.

My question: “My” proof technique makes the accounting method very close (almost identical) to the potential method. The money on the account defines more or less a potential function. From a pedagogical perspective (which is what I am interested in, of course), what is the best solution?

• Present both methods as completely distinct, and maybe avoid “my” proof technique;
• Present both methods separately and show that they are two ways of presenting the same idea;
• Present the potential method, and then the accounting method as a way to define a potential function;
• Something else…