Why we need amortized analysis?
We always use worst case analysis (big-O) to calculate time complexity. However, have you ever thought that we would overestimate the cost? In specific algorithm, there is a sequence of operations with different costs. You might said that time complexity would be
number of operations * the largest cost of operations. For example, there are three kinds of operations for stack: push, pop, and multipop(n) which would pop out n elements. Based on knowledge of worst case analysis, the ith operation takes O(n) of time complexity in worst case, then the sequence of n operations takes O(n^2) time. But how if there is only one O(n) and the rest of them are all O(1)? We have overestimate the cost of the case! Now, we know that the worst case bound is not tight because the expensive operation might not occur frequently. In amortized analysis, if sequence of operations have different costs, we can distribute the high one to the low ones. Following sections are three methods of amortized analysis.
Amortized analysis helps us to obtain a more accurate bound of worst case…
Sum up the all cost of operations (
T(n)) and divide it by number of operations
n. Take the stack for example,
In aggregate method, we would get same amortized cost on each operations.
Save credits from the operations which takes less cost and used for future operation that take more cost. Take the stack for example,
Be careful, check that you won’t run into bankruptcy no matter which situation. If amortized cost is bigger than actual lost, the difference becomes a credit, otherwise it would become a withdrawl. What is different from aggregate method, each operation can have different amortized cost.
The core of potential method is potential function Φ(Di)
phi. Do: the initial state of data structure, Di: the state after ith operation, ci: the actual cost of ith operation, ci’: the amortized cost of ith operation which is
ci + Φ(Di) - Φ(Di-1). Take the stack for example:
What’s different from accounting method, the credit is assigned to data structure itself.
Is it possible for amortized cost to be negative? Yes, it is possible for single operation to have negative amortized cost. But for n operations, total amortized cost should always be non-negative.