Define amortized analysis. Briefly explain its two techniques.
Answers
Answer:
In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. ... Amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm.
Explanation:
Analysis of Algorithm | Set 5 (Amortized Analysis Introduction)
Amortized Analysis is used for algorithms where an occasional operation is very slow, but most of the other operations are faster. In Amortized Analysis, we analyze a sequence of operations and guarantee a worst case average time which is lower than the worst case time of a particular expensive operation.
The example data structures whose operations are analyzed using Amortized Analysis are Hash Tables, Disjoint Sets and Splay Trees.
Let us consider an example of a simple hash table insertions. How do we decide table size? There is a trade-off between space and time, if we make hash-table size big, search time becomes fast, but space required becomes high.
Dynamic Table
The solution to this trade-off problem is to use Dynamic Table (or Arrays). The idea is to increase size of table whenever it becomes full. Following are the steps to follow when table becomes full.
1) Allocate memory for a larger table of size, typically twice the old table.
2) Copy the contents of old table to new table.
3) Free the old table.
If the table has space available, we simply insert new item in available space.
HOPE IT'S HELP U
Answer:
Amortized analysis is a method of analyzing the costs associated with a data structure that averages the worst operations out over time. ... There are three main types of amortized analysis: aggregate analysis, the accounting method, and the potential method.