Amortized analysis for datastructures having early high cost and then low cost

Question

When reading about the accounting method of amortized analysis, it was mentioned that the bank balance cannot go negative. But what if I have some data structure (DS) which takes initial high cost and subsequent low costs to nullify the effect of high cost. The proof for the same will require some loan from the bank and then the debt gets paid in future by the subsequent low cost operation. How are we to do amortized analysis for such data structures ?

PS: I don't have example data structure for the above, and the doubt is hypothetical.

Answer 1

Not every algorithm has a good amortized complexity, and in cases where "loans from the bank" would be required, the algorithm probably doesn't. To find the correct amortized cost, you have to increase the cost until you have a value that guarantees you never go negative - even if this overestimates the average cost.

The idea with the accounting method is that if each operation has an "amortized cost of $T$", which corresponds to adding a credit of $T$ and then spending some of the existing credit, then no matter how many operations you have to do - which we may not know in advance - $k$ operations will take at most $T \cdot k$ steps. So the average cost of each operation is at most $T$.

If you have to "take out a loan" to cover the cost of an initial high-cost operation, that gets you in trouble when only few operations are necessary. For example, say the initial operation takes $1000$ seconds, and every subsequent operation takes $1$ second.

• In a world of wishful thinking, if you were guaranteed that at least $1000$ operations would happen, you could indeed say something like "the first operation takes out a loan of $1000$ seconds, then does its thing. Every subsequent operation takes $1$ second, then pays $1$ second to the loan, for a total cost of $2$ seconds per operation". Indeed, if at least $1000$ operations happen, then the average cost of $k$ operations is $\frac{1000 + (k-1)}{k} = 1 + \frac{999}{k} < 2$ seconds.
• But amortized analysis is intended to address situations where there is no such guarantee. So it's possible that there's only $2$ operations, for an average cost of $\frac{1000 + 1}{2} = 500.5$ seconds.

In a sense, we can still do amortized analysis for this example: we can say that each operation has an amortized cost of $1000$. Then we never go negative. If there happen to be lots of operations, we've badly overestimated the time they'll take: but this is the best guarantee we can make without knowing the number of operations that will happen.

We might be able to improve the algorithm to have a better amortized cost. Maybe we can make the initial operation take only $100$ seconds, but have to redo it every $100$ steps. This is the sort of trade-off that makes your average running time worse in the long run (if there is a long run) - but gives you a better amortized running time, because when very few operations are done, the average time per operation is much smaller.