Amortized Analysis

worst-case bound >= amortized bound >= average-case bound

Three ideas

Aggregate analysis

This idea is to show that a sequence of n operations takes time in the worst-case is still O(?) in average. So we could sum up the total time which the n operations will take in the worst case, then find the average time complexity.

Accounting method

Buiding a saving account.

Appropriate reduction in the time spent per session, when the amortized time cost is larger than the actual cost, you can get the credit. In the opposite, you will lose the credit. After the last operation, your credit must be positive.

Potential method

Having a appropriate potential function is quite important.

is a potential function. Such as in splay tree amortized analysis, this function is