Ways to Prove Amortized Bounds
Amortized analysis seems pretty easy—work out the worst-case time for \( m \) operations, divide by \( m \), done.
Yes, if the operations are all the same. But what if people can mix different kinds of operations, like
push_back()andpop_back()?
Or
insertandexistsfor splay trees.-
Oh…
Let's look at some different ways to prove amortized bounds.
Aggregate Method
Working out the time for \( m \) operations and dividing by \( m \) is known as the aggregate method. This approach is really only practical if all the operations are essentially the same.
We can use other approaches when we have a mix of different operations to deal with.
Banker's Method
The idea of amortization predates computers by a lot. It has a long history as an accounting method for ensuring that a large cost is paid for over a long period of time.
In the banker's method we treat time like money, and assign a charge for each externally visible action (like push_back()) and use that charge to set aside money to pay for internal operations. The goal is to show that if we need to do many operations at some point in the future, we'll have set aside enough money to pay for them.
Our card-game analogy and operation-coloring example provided a good way to see how we could make those kinds of arguments. Often these arguments focus on conceptually putting the money on certain parts of the data structure to show it's paid for (e.g., putting $1 on each array element).
Physicist's Method
The physicist's method is another approach. Here, we treat time like energy. We show that there is a potential function that maps situations to numbers representing the “potential energy” in that situation. Some operations use energy and some increase energy but we can prove that there is always enough energy in the system to perform each operation.
Which ones do I need to know?
-
We won't expect you to perform any new amortized analysis at all. But you'll see these methods if you take an algorithms class.
Hay! What about analyzing splay trees?
-
Again, that's for future classes.
-
Our goal here is to have you understand what what it means in practice when an operation is described as taking amortized time.
-
So what are our takeaways?
Takeaways
Amortized time is useful when we have a data structure that operations are usually quite cheap to perform, but occasionally we need to do something expensive (like copying a large array).
- Just stating the worst-case time per operation would be misleading, as it would overemphasize the rare expensive operations.
- Instead, amortized time promises that the worst-case time of a sequence of operations is bounded by the sum of the amortized times of the individual operations.
- But it only applies to the total time of the sequence of operations from the very beginning.
Amortized time provides a useful fiction: even though some operations are expensive and some are cheap, an amortized bound spreads the cost evenly, and lets us focus on the big picture, the total execution time of the program.
-
But what if the total execution time of the program of the program isn't what I care about? Maybe I'm writing a game and a long operation might make the game stutter or hang for a moment?
-
In that case, you do care about the worst-case time for a single operation. A guarantee about total execution time won't help you much at all.
-
We'll think a bit about these kinds of choices on the next page.
If a splay tree requires \( \mathrm{O}(\log n) \) amortized time per operation, we can restate that as saying, “When thinking about the entire time the program runs, we can pretend that this operation (and all the the other inserts) took \( \mathrm{O}(\log n) \) time. And that time might even be an overestimate.”
Remember, the definition of amortized time is
Definition: When operations have a specified amortized time, it means that the total time of all the operations performed up until now is bounded by the sum of the amortized times of the individual operations.
To be clear, this time is an upper bound.
(When logged in, completion status appears here.)