« Monkeys on Trees IV | Main | Monkeys on Trees II »

Monkeys on Trees III

Amortization is an averaging technique over a sequence of operations as opposed to taking worst case of individual operations. Here the operations are from the ADT point of view and not from the intrinsic cost of machine level operations. Moreover, in a macro coded machine, the intrinsic cost of a machine level operation is also an ADT operation at a finer granularity!

It is the right time to draw an analogy,  between  Discrete Dynamic Programming(DDP) and Amortized Analysis ! In DDP we want to avoid any duplication of work. If anything we computed already, then we would like to use the result again and and again. Think about Fibonacci sequence computation, for example. In amortized analysis we want avoid adding unnecessary or somewhat absurd complexity, and look at the big picture (i.e. the whole sequence of operations), and average them out, not a probabilistic average.

There are three main types of Amortizations techniques in use: Aggregate; Accounting; and Potential. There is no such restrictions for picking up some methods besides those three, as long as it make real sense for the underlying analysis. As we know, it does not impact the implementation, and should not impact at all.

At this point it is enogh to know that Aggregate method assigns average costs to each operation types, and intuitive in nature. One remark deserves here, is that Total Average cost and individual operation type cost.  Whereas, in Accounting and Potential methods, individual operation type cost could be different in the averaging process. Please take a look at some standard textbook on Algorithms.

We will emphasize Potential method, since it is one of the main analysis type for Online Algorithms. And it also have interplays with Probabilistic algorithms. A probablistic algorithm has to tackle the probabilistic bound, as well as the complexity bound. Lot of such algorithms are basically from limiting sense, so it is better to think from the limit theorem, limiting probability etc...

Posted on Wednesday, May 7, 2014 at 05:05PM by Registered CommenterProkash Sinha | Comments Off