Same as accounting method: something prepaid is used later.

__THE
POTENTIAL METHOD:__

•
Same as accounting method: something prepaid is
used later.

•
Different from accounting method

– The prepaid work not as credit, but as
“potential energy”, or “potential”.

The
potential is associated with the data structure as a whole rather than with
specific objects within the data structure.

•
Initial data structure *D*_{0}, *n*
operations, resulting in *D*_{0},
*D*_{1},…, *D _{n}* with costs

•
A potential function F: {*D _{i}*}

•
F(*D _{i}*) is called the potential
of

•
Amortized cost *c _{i}'*
of the

*c _{i}' *=

å_{i}_{=1}^{n}* c _{i}' = *å

= å_{i}_{=1}^{n}*c _{i} *+

•
If F(*D _{n}*) ³ F(

•
But we do not know how many operations, so F(*D _{i}*) ³ F(

•
It is convenient to define F(*D*_{0})=0,and so F(*D _{i}*) ³0, for all

•
If the potential change is positive (i.e., F(*D _{i}*) - F(

**Potential method: stack operation**

•
Potential for a stack is the number of objects in
the stack.

•
So F(*D*_{0})=0, and F(*D _{i}*) ³0

•
Amortized cost of stack operations:

– PUSH:

•
Potential change: F(*D _{i}*)- F(

•
Amortized cost: *c _{i}'*
=

– POP:

•
Potential change: F(*D _{i}*)- F(

•
Amortized cost: *c _{i}'*
=

– MULTIPOP(*S*,*k*): *k'*=min(*s*,*k*)

•
Potential change: F(*D _{i}*)- F(

•
Amortized cost: *c _{i}'*
=

•
So amortized cost of each operation is *O*(1), and total amortized cost of *n* operations is *O*(*n*).

•
Since total amortized cost is an upper bound of
actual cost, the worse case cost of *n*
operations is *O*(*n*).

**Potential method: binary counter**

•
Define the potential of the counter after the *i*th INCREMENT is F(*D _{i}*) =

•
Let us compute amortized cost of an operation

– Suppose the *i*th operation resets *t _{i}*
bits.

– Actual cost *c _{i}* of the operation is at most

– If *b _{i}=*0

– If *b _{i}>*0,
then

– In either case, *b _{i}*£

– So potential change is F(*D _{i}*) - F(

– So amortized cost is: *c _{i}'* =

•
The total amortized cost of *n* operations is *O*(*n*).

•
Thus worst case cost is *O*(*n*).

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

Programming and Data structures : Advanced Non-Linear Data Structures : Potential Method |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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