Amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations.

__AMORTIZED
ANALYSIS:__

Amortized
analysis is a method of analyzing algorithms that considers the entire sequence of operations of the
program. It allows for the establishment of a worst-case bound for the
performance of an algorithm irrespective of the inputs by looking at all of the
operations.

•
Not just consider one operation, but a sequence of
operations on a given data structure.

•
Average cost over a sequence of operations.

•
**Probabilistic
analysis:**

– Average case running time: average over all
possible inputs for one algorithm (operation).

– If using probability, called expected
running time.

•
**Amortized
analysis:**

– No involvement of probability

– Average performance on a sequence of operations,
even some operation is expensive.

– Guarantee average performance of each operation
among the sequence in worst case.

**Three Methods of Amortized Analysis:**

•
**Aggregate
analysis:**

– Total cost of *n* operations/*n*,

• **Accounting method:**

– Assign each type of operation an (different)
amortized cost overcharge some operations, store the overcharge as credit on
specific objects, then use the credit for compensation for some later
operations.

•
**Potential
method:**

– Same as accounting method.

– But store the credit as “potential energy”
and as a whole.

**Example for amortized analysis:**

•
**Stack
operations:**

– PUSH(S,x), *O*(1)

– POP(S),
*O*(1)

– MULTIPOP(S,*k*), min(*s*,*k*)

while not STACK-EMPTY(S) and *k*>0 do POP(S)

*k*=*k*-1

•
Let us consider a sequence of *n* PUSH, POP, MULTIPOP.

– The worst case cost for MULTIPOP in the sequence
is O(*n*), since the stack size is at
most *n*.

– Thus the
cost of the sequence is *O*(*n*^{2}). Correct, but not tight.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Programming and Data structures : Advanced Non-Linear Data Structures : Amortized analysis |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.