I was reading CLRS and it said in the chapter for the accounting method (for amortized analysis):
the total credit associated with the data the structure must be nonnegative at all times.
where total credit is defined as:
The total credit stored in the data structure is the difference between the total amortized cost and the total cost.
It also mentions the following:
If we denote the actual cost of the ith operation by $c_i$ and the amortized cost of the ith operation by $\hat{c}_i$, we require:
$$ \sum^n_{i=1} \hat{c}_i \geq \sum^n_{i=1} c_i$$
for all sequences of n operations.
CLRS does provide an explanation of why it requires it but I am not sure I understand it. I will paste its explanation and explain my confusion:
If we ever were to allow the total credit to become negative (the result of undercharging early operations with the promise of repaying the account later on), then the total amortized costs incurred at that time would be below the total actual costs incurred; for the sequence of operations up to that time, the total amortized cost would not be an upper bound on the total actual cost. Thus, we must take care that the total credit in the data structure never becomes negative.
So this is what I am confused about. When it says it requires $ \sum^n_{i=1} \hat{c}_i \geq \sum^n_{i=1} c_i$ to hold for all operations, does it implicitly also mean that it requires it for all $n \in \mathbb{N}$? i.e. its for all sequences of $n$ operations for all $n$?
What would be the deal if it didn't hold for all $n$? I tried reasoning this and I think it means that there exists some sequence that overall, is undercharged if we were to stop doing stuff at the end of that sequence. Thus, we wouldn't actually have a valid run-time analysis for this specific sequence of $n$ operations. Right?
I do think that it does mean for all natural numbers $n$ too. The reason I think this is because the way I think of the accounting method is that we have credit for later operations. If it was ever negative it means that some operation on the data structure at some point doesn't have actual enough "prepaid work" for some operation. Is this right or am I missing something?
Is the goal just that at all times for any sequence of any time that we always have an upper bound on the cost of $n$ operations? Regardless weather its charging, accounting, potential method etc, the goal is that always we have an upper bound on the cost of a sequence of $n$ operations?
So in this line of thought, if we do the potential method with:
$$ \hat{c}_i = c_i + \Phi(D_i) - \Phi(D_{i-1})$$
then because of the telescoping property, do we require for all sequences of operations that:
$$ \Phi(I_n) - \Phi(I_0) \geq 0$$
Since:
$$ \sum^n_{i=1} \hat{c}_i = \sum^n_{i=1} ( c_i + \Phi(D_i) + \Phi(D_{i-1}) ) = \sum^n_{i=1} c_i + \Phi(D_n) - \Phi(D_{0})$$
since we need: $ \Phi(I_n) - \Phi(I_0) \geq 0$
