We've performed amortized analysis at some point or another in our lives without actually knowing it. A few lame examples follow:
- For the stock broker: Purchasing shares at a lower price to average out the cost price of all the holdings of a given stock
- For the fitness enthusiast: Working out thrice as much at the gym today because [s]he missed 2 days before today
- For the reader: Reading a few more pages of a book so that you can take a break tomorrow and still complete it on time
- Ex-1: You're jogging 16 miles every day for 8 days, and your friend jogs 8 miles and 24 miles on every odd and even numbered day respectively (starting from day #1). Who jogs more over a period of 8 days? Here is a graphical representation of how much you and your friend ran over a period of 8 days:
- Ex-2:You're jogging 16 miles every day for 7 days, and your friend jogs in the following manner:
Day Miles Jogged 1 2 2 2 3 4 4 8 5 16 6 32 7 64
- Ex-3: You're playing a game where you have a graph and you start at the node with the symbol S and finish at the node with the symbol F. The constraints on your moves are that you must take EXACTLY ONE blue coloured edge in every move, but you can take as many (or zero) red coloured edges in a move. A move contains a combination of red and blue edges.
An example graph is shown here:
If you got this far, and were able to solve all the exercises - congratulations! - you've understood what amortized analysis is all about! And as an added benefit, Ex-2 is how one would go about analyzing the insertion cost for Dynamic Arrays, and Ex-3 is actually how one would analyze the running time for the KMP string matching algorithm!