patternMinor
Does amortized complexity always equal to worst case complexity divided by n?
Viewed 0 times
caseequalalwaysdivideddoesamortizedworstcomplexity
Problem
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
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
Solution
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$:
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.
- If $n = N$, create a new array of length $2N$, copy the old array into the new array, and free the old array.
- 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.
Context
StackExchange Computer Science Q#35419, answer score: 7
Revisions (0)
No revisions yet.