Potential method

In algorithms, the potential method is a method used to analyze the amortized time and space complexity of an algorithm. It can be thought of as a generalization of the accounting method and the debit method. It is useful in cases where it is hard to assign credit to specific elements of the structure.

The method

The potential function phi is set to be a positive-valued function from states of the data structure in question. If c_i represents the actual cost of the "i"th operation, which updates the data structure from state A_{i-1} to state A_i, then the "effective cost" d_i of this operation is defined to be d_i = c_i + phi(A_i) - phi(A_{i-1}) (i.e., the effective cost is the actual cost plus the difference in potential).

If phi is chosen so that the starting state of the data structure has potential 0, then the sum of the effective costs d_1,dots,d_n is greater than or equal to the sum of the actual costs c_1,dots,c_n. So if an upper bound on the effective cost of each operation can be shown, this implies an upper bound on the total cost of n operations, which gives an upper bound on the amortized cost per operation.

Sample applications

Table expansion

Determining the amortized cost of table expansion can be solved using the potential method. Let the potential function be the number of occupied cells minus the number of vacant cells. A regular insert incurs O(1) cost and increases the potential by O(1); thus, the "effective cost" of a regular insert is O(1). An insert that causes reallocation incurs cost O(n) but decreases the potential by O(n), giving an effective cost of O(1) for this operation. Since each type of operation has O(1) effective cost, this implies an amortized cost of O(1) as well.

See also

* Amortized analysis
* Fibonacci heaps

External links

* [http://www.cs.utexas.edu/~vlr/s06.357/notes/lec16.pdf Amortized analysis in the University of Texas]

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Discrete delta-potential method — The discrete delta potential method is a combination of both numerical and analytic method used to solve the Schrödinger equation the main feature of this method is to obtain first a discrete approximation of the potential in the form: V(r) = ∑… …   Wikipedia

  • nodal-potential method — mazgų potencialų metodas statusas T sritis automatika atitikmenys: angl. nodal analysis; nodal solution; nodal potential method; nodal voltage method; node voltage method vok. Knotenspannungsmethode, f rus. метод узловых потенциалов, m pranc.… …   Automatikos terminų žodynas

  • Metra potential method — The metra potential method (MPM) (Méthode des potentiels Métra) was devolloped by french researcher Bernard Roy in 1958 for the construction of the French paquebot France and of the first French nuclear power plant. MPM is a means of describing… …   Wikipedia

  • nodal-potential method — mazginių potencialų metodas statusas T sritis radioelektronika atitikmenys: angl. nodal potential method; nodal voltage method vok. Knotenspannungsmethode, f rus. метод узловых потенциалов, m pranc. méthode nodale, f …   Radioelektronikos terminų žodynas

  • retarding potential method — vėlinamojo potencialo metodas statusas T sritis radioelektronika atitikmenys: angl. retarding potential method vok. Verzögerungspotentialmethode, f rus. метод задерживающего потенциала, m pranc. méthode de potentiel retardateur, f …   Radioelektronikos terminų žodynas

  • Metra Potential Method — Die Metra Potential Methode (MPM, auch Tätigkeits Knoten Darstellung oder Vorgangs Knoten Darstellung genannt) ist eine Netzplantechnik sowie eine Methode der Graphentheorie zur Berechnung von Netzplänen. Es handelt sich hierbei um ein sehr… …   Deutsch Wikipedia

  • self-potential method — | ̷ ̷ ̷ ̷| ̷ ̷ ̷ ̷ noun : a method of electrical prospecting in which the electromotive forces existing in and around an ore body are measured at the surface …   Useful english dictionary

  • Potential theory — may be defined as the study of harmonic functions. Definition and comments The term potential theory arises from the fact that, in 19th century physics, the fundamental forces of nature were believed to be derived from potentials which satisfied… …   Wikipedia

  • Method of image charges — The method of image charges (also known as the method of images and method of mirror charges) is a basic problem solving tool in electrostatics. The name originates from the replacement of certain elements in the original layout with imaginary… …   Wikipedia

  • Method engineering — Not to be confused with Methods engineering, a subspecialty of Industrial engineering Example of a Method Engineering Process. This figure provides a process oriented view of the approach used to develop prototype IDEF9 method concepts, a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.