3
$\begingroup$

Is it true that given any operation that takes O(f(n)) amount of time, we do this n times in a process, then the amortized cost is O(f(n))/n?

I'm confused because this statement is so simple and applicable, I don't see the need for accounting method or potential method if we can just divide the worst case operation i.e. enlarging a dynamic array or multipop by the times we want the operation to be perfornmed

$\endgroup$
  • $\begingroup$ Can you show me exactly how accounting method takes care of the operation sequence versus aggregate analysis? $\endgroup$ – Olórin Dec 17 '14 at 3:50
6
$\begingroup$

No, if all we know about an operation is that it takes $O(f(n))$ times, then its amortized time is also $O(f(n))$. Sometimes, however, it is the case that while the worst-case running time is $O(f(n))$, the worst case cannot happen all the time. A good example is dynamic arrays. Suppose we want to maintain an increasing array, but we don't know in advance how big the array is going to be. Therefore we use the following algorithm for inserting an element to the array; in the algorithm, $N$ is the current length the array, and $n$ is the current number of elements in the array, both initialized to $1$:

  1. If $n = N$, create a new array of length $2N$, copy the old array into the new array, and free the old array.
  2. Add the new element to the end of the array.

When $n < N$, this operation takes time $O(1)$. However, when $n = N$, we need to copy the entire array, and so it takes $O(n)$. The running time of insertion is therefore not even bounded! Nevertheless, the amortized running time of insertion is $O(1)$. Intuitively, the reason is that the expensive copying operation is very rare.

Indeed, suppose we perform $m$ insertion operations. The expensive operation occurs at the first, second, 4th, 8th, 16th, and so on, insertions, and involve copying $1,2,4,8,16,\ldots,M$ elements, where $M \leq m$. The total number of elements copied is $1+2+4+8+16+\cdots+M = 2M-1 < 2m$, and so the total running time is $O(2m) + O(m) = O(m)$, the first summand corresponding to the copying operations, the other corresponding to the cheap second step of the algorithm above. The amortized running time is therefore $O(m)/m = O(1)$.

There are several methods to prove upper bounds on the amortized running time, such as the accounting method and the potential method. These are just mathematical tricks that are supposed to help you analyze algorithms, though as the example analyzed above shows, you don't really need to use them formally in order to analyze the amortized running time; it's enough to use the definition of amortized running time. In more complicated cases these methods could be more helpful, though I feel that they are being taught mostly for historical reasons such as their inclusion in some influential textbook.

$\endgroup$
  • $\begingroup$ like late night long answers, will give a good read in the morning I promise $\endgroup$ – Olórin Dec 17 '14 at 8:03
1
$\begingroup$

The method of $O(f(n))/n$ is often called the aggregate analysis. It is useful when we are clear about the operation sequence. The dynamic array and binary counter are typical examples of this kind.

However, sometimes (maybe usually) we don't know the operation sequence and are not able to obtain the $O(f(n))$. Then we need other techniques such as accounting method or potential method.

For the accounting method, you can refer to this post: How can I make sense of amortized accounting method?.

I am not quite familiar with the potential method. It is more sophisticated. Waiting for other answers about it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.