2
$\begingroup$

I cannot really find a source that does not use the same examples provided by CLRS. I need a simpler example than MULTI-POP example. Could someone provide an example and explain me:

a) What is the difference between worst-case analysis and amortised analysis?

b) What is the difference between average-case analysis and amortised analysis?

c) In plain English(with using minimal notations), how can we provide a complexity(especially I am interested in potential method)

$\endgroup$
2
$\begingroup$

I'll just answer a) and b) because I don't know the potential method.

About a) Worst case analysis only considers a single operation. If you want to know how expensive your algorithm is in its worst case, you need to find the worst case cost of every single operation and then count how often each of them is executed. For example, you may have come about a structure called "dynamic array", which is very similar to an ArrayList in Java. The way that structure operates is that internally it has an array, and it doubles in size once it's full, copying everything into the new array.

Now what's the worst case cost for an insert operation into that structure? The worst that can happen is that you have to double the array that contains $n$ elements, so you get a worst case cost of 1 operation (!) of $\mathcal{O}(n)$. If you insert $n$ elements, this gives you a worst case running time of $\mathcal{O}(n \cdot n) = \mathcal{O}(n^2)$.

Obviously that is far too pessimistic. We know that we only have to double every $2^k$ steps, because with every time we double the size of the array, it'll take twice as long until we need to double it again. Here is where amortized analysis comes into play: you know that there are some expensive operations, but you also know that they happen comparatively rarely, so you try to see whether the "naive" worst case analysis can be improved with a little bookkeeping. In order to do this reasonably, you don't consider a single operation anymore, you consider a sequence of operations, usually of length $n$.

Maybe you have read about the accounting method: you have an account where you can "save up" time, and every operation is allowed to take "time" out of the account, but no more than is in the account. The idea behind this is that the many cheap operations "help pay" for the few expensive ones, and if we distribute the cost that way, we can get a better analysis (that is still a true upper bound, i.e. the actual complexity is still below the amortized complexity in all cases).

How would that work in the case of the dynamic array? Every "cheap" insert is just one write operation to the array, so that costs us $1$ unit of time. Every "expensive" operation costs us $k$ units where $k$ is the number of elements in the array at that time. Now we would like the cheap inserts to share the cost of the expensive one that they help produce. This can be done if every cheap insert, in addition to paying its own $1$ unit of cost, contributes another $2$ units to the account, because this way, the inserted element pays for the copying of itself and a second one that will be copied when we double. This means that for every expensive insert we have, there will be at least $k$ units of time on our account, and we can pay for it using the money in the account only, so the actual cost of the expensive insert goes down to $k-k = 0$ (because it doesn't actually cause work that hasn't already been paid for, it's paid for with the time that was "saved up" by the cheap inserts using the account savings). How does this help us? Now every cheap insert costs us $1+2=3$ units, and every expensive insert costs us $k-k =0$ units, giving both an amortized cost of $\mathcal{O}(1)$. If we want to calculate the amortized cost of inserting $n$ elements now, we get $\mathcal{O}(1 \cdot n) = \mathcal{O}(n)$, and this is still an upper bound on the actual cost that any input can produce.

About b) While amortized analysis still gives you an upper bound on the actual cost of an algorithm, average case analysis doesn't guarantee that; there may be inputs where the actual cost is above the average case cost. But that's not a problem for average case analysis, because it just tells you what the cost of running your algorithm typically is, meaning as an average of the cost of all possible instances of size $n$.

$\endgroup$
  • $\begingroup$ I see the point here, so whenever we do amortised analysis, we have to find a cheap operation(usually O(1) to O(n) ) and then count(for accounting method) this operation as a constant by dividing the actual cost of the expensive operation into this? So amortised analysis cannot be applied to places like adding element to an unsorted linked list. $\endgroup$ – Sarp Kaya Oct 28 '13 at 21:58
  • $\begingroup$ @SarpKaya That's the basic idea, distributing the cost of few expensive operations among many cheap ones; it doesn't have to be $\mathcal{O}(1)$ and $\mathcal{O}(n)$, you could also have a cheap operation that costs $\mathcal{O}(n^2)$ and an expensive one that costs $\mathcal{O}(n^4)$ but only happens every $n^2$ steps, then you could also distribute down to $\mathcal{O}(n^2)$. In general, for constant analysis you can't only consider a single operation, you will always have to consider a sequence of many operations in order to do the distributing thing. $\endgroup$ – G. Bach Oct 28 '13 at 22:40
  • $\begingroup$ @SarpKaya About a) and b) just to quote CLRS: Amortized analysis differs from average-case analysis in that probability is not involved; an amortized analysis guarantees the average performance of each operation in the worst case. However compared to traditional worst-case analysis, amortized analysis is analyzing any operation sequences. $\endgroup$ – hengxin Oct 29 '13 at 6:55

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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