SE250:HTTB:WIP:Amortized Time Analysis
Things that can go in here
- Intro?
- Usefulness?
- Aggregate Analysis?
- Accounting Method?
- Potential Method?
- Examples?
- Quiz/Questions?
Amortized Time Analysis:Introduction
Amortized Time Analysis involves analyzing time-averaged costs for a sequence of operations. Amortized Time Analysis is basically used to predict the worst-case scenario of a sequence of operations performance wise (Big-O notation is involved in the prediction). The basic idea is that a worst case operation can alter the state in such a way that the worst case cannot occur again for a long time, thus "amortizing" its cost. Techniques used in Amortized Time Analysis include:
- The Aggregate Analysis
- The Accounting Method
- The Potential Method
(Intro by:Srag014 21:08, 1 June 2008 (NZST))
The Aggregate Analysis
The Aggregate Analysis is one of the methods commonly used to derive the amortized bounds of an piece of algorithm. The amortized cost for each single operation is calculated by taking the average of the total running time. Hence T(n)/n, where n is the number of operations, and T(n) is the the worst case running time for a sequence of n operations.
The Accounting Method
Using the accounting method:
- We start off by assigning each operation in the algorithm with an specific amount of charge, this amount of the charge is called amortized cost.
- Different operations will be assigned with different amortized costs.
- Amortized cost could be greater or less than the actual cost of the operation.
- As we go through each operation in the algorithm, if the amortized cost for an operation is greater than its actual cost, the difference is then stored as credits to use by the operation having amortized cost less than actual cost.
The Potential Method
- The idea of the potential method is the same as the accounting method, but using potential energy as the cost.
- The potential is associated with the data structure as a whole rather than with specific objects within the data structure, so it is useful in certain situation where it is difficult to assign a specific amortized cost for a single operation.
Dynamic tables
Aynamic table is an example using the potential method to analyze a dynamically expanding and contracting table.
In a hash table, the size of table should be as small as possible, how large is enough if it stores more data? How about if we don’t know the number of data we going to store? So, dynamic tables can solve the problem. Whenever the table overflows, “grow” it by allocating (in malloc )a new, larger table. Copy all elements from the old table (memory) to the new one (reallocated), and free the storage for the old table. Using amortized analysis, we shall show that the amortized cost of insertion and deletion is only O(n)/n=O(1).
The Charging Method
- A more less used method of analysis, but still used when amortized analysis involves charging costs for certain divisions that had occurred before the present state. Comments on this analysis method refer to it being similar to the taxation method but in this we separate each part into its tax, where as the taxation method focuses on the whole collection. This analysis helps as it charges the cost of something that’s will occur in the future runtime of the program. For example - It will charge for clearing a bit as soon as you set it form 0 to 1. So in the future lifetime of the program we don’t need to charge for the same operation for the amortized time analysis
Conclusions
- Amortized costs can provide a clean abstraction of data-structure performance.
- Any of the analysis methods can be used when an amortized analysis is called for, but each method has some situations where it is arguably the simplest.
- Different schemes may work for assigning amortized costs in the accounting method, or potentials in the potential method, sometimes yielding radically different bounds.
Screen Casts
Table with screencast descriptions shown below:
| User | Description |
|---|---|
| srag014 | An example of ATA + some basics |
| shua066 | An example of ATA |
Quiz
References
- Wikipedia page on Amortized Time Analysis
http://en.wikipedia.org/wiki/Amortized_analysis
- Some Notes from the School of computer Science at Carneige Mellon University
http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-f00/www/lectures/lect0919
- from IUPUI Indiana university-purdue university indiannpolis's CS lecture
- from Princeton university’s COS 423 lecture
http://www.cs.princeton.edu/~wayne/cs423/lectures/amortized-4up.pdf
| User | Description |
|---|