What is the Potential Method?

The complexity of the algorithm model emphasizes the potential method. This method is useful for examining a data structure's amortized time and space complexity.

A function $\phi$ is used in the potential method. The potential method was selected to translate data states to non-negative values. The function $\phi \left(S\right)$ signifies work that the amortized analysis has taken into account. However, if S is regarded as such state of the data structure which has not yet been done. As a result, $\phi \left(S\right)$ can calculate the amount of accumulated potential energy in that scenario. Before a data structure is initialized, its potential value is considered to be zero. Alternatively, $\phi \left(S\right)$ could represent the degree of disorder in state S or the difference between itself and a perfect state.

Example-

The potential function $\phi$ (Phi) defined on the data structure's state must satisfy the following essential specifications.

• $\phi \left(a_0\right) = 0,$where $a_0$ signifies the data structure's initial state.
• $\phi \left(at\right)\ge 0$ for all other states of the data structure that occur throughout the course of computation.

The potential function is entirely reliant on the present state of the data structure, independent of the computations that resulted in that state.
As a result, the amortized time of a process is specified as:

$c + \phi (a\text{'}) - \phi \left(a\right),$

where $c$ represents the original cost of the operation and $a$ and $a^{\text{'}}$ represent the initial (state before performing operation) and final states (state after performing the operation) of the data structure. So, amortized time describes the actual time and the change in potential. The potential function must be defined such that the amortized time of each operation must be small. Difference in potential will be positive for low cost operations and it will be negative for high cost operations.

The Accounting method

In the accounting method of amortized analysis, various charges are available that are associated with various activities. The cost of these processes is more or less charged. So the amount that is charged with the operation is called the amortized cost. The difference between the amortized and real costs is awarded to specified objects in the data structure when the amortized cost reaches the maximum cost. Designers can use credit to continue paying for activities when the amortized cost is lower than the actual cost. As a result, the amortized cost of an activity can be divided into its actual cost and credit that is either deposited or used up. On the other hand, the aggregate method employs the same amortized cost for all processes.

The amortized costs of an operation must be carefully chosen. If researchers wish to use amortized costs to demonstrate that the average cost per operation is low in the worst scenario, the total amortized cost of a set of activities must represent an upper bound that is available on the complete actual cost set of activities. Further, like with the aggregate method, this connection must apply for all procedure cycles. As a result, the data structure's total credit must always be positive because it represents the amount by which total amortized costs surpass total real costs. The total amortized expenses involved at a certain time would be less than the total real costs incurred if the entire credit was ever permitted to become negative. In such an instance, the total amortized cost for the series of procedures up to that point would not be an upper constraint on the entire real cost. As a result, designers must ensure that the data structure's total credit never falls below zero.

Amortized analysis

Amortized Analysis is applied to algorithms in which one or more operations are extremely slow, but most of the actions are faster. Review a series of operations in amortized analysis to ensure that the worst-case average time is less than the worst-case time of particularly expensive activity. Operation performed on the data structures such as splay trees, hash tables, and disjoint sets are analysed by the Amortized analysis.

When using hash tables, there is a trade-off between space and time requirements. Increasing the size of the hash table reduces search time. At the same time, it increases the amount of space required.

The use of dynamic tables is the solution to this trade-off situation. When the table becomes too small, the aim is to expand it. When the table reaches its maximum capacity, the steps to take are as follows.

The n-insertion operation's time complexity is determined as follows.

The worst-case cost of an insertion is $O\left(n\right)$.  The cost of n insertions in the worst-case scenario is $n*O\left(n\right)$ or $O\left(n^2\right)$. For n insertions, this approach is suitable for determining an upper bound. But, it need not be a tight upper bound. Because most of the insertions do not require $\theta \left(n\right)$ time.

Thus, the dynamic table has O(1) complexity for the insertion operation.

A few key points are listed below.

• A salaried person's expenses can be understood as the amortized cost of a series of procedures. The person's average monthly spending is less than or equal to their earnings. However, by acquiring a car or something else, he can spend a lot of money in a specific month. Throughout those months, he keeps the costs down to adjust for the pricey month.
• The amortized analysis carried out for the insertion operation of dynamic table uses aggregate method. Other methods are also available for amortized analysis namely potential method and accounting method.
• The concept of probability is not used in amortized analysis.

Amortized time

Amortized time is a technique of expressing time complexity when an algorithm has extremely bad time complexity only occasionally, in addition to the time complexity that occurs most of the time.

An Array List is a data structure. It may be extended to hold an array. Another Stack Overflow definition is the average time taken per action if you do many of them. When an array's capacity is reached, a new array is created. The size of this array is double the size of the previous array. And after that, it copies all the elements of the previous array to the new array. Array List has two temporal complexity: O(1) and the other is O(n).

When the array has not reached its maximum capacity and there is still space to insert objects.

In this scenario, the item to be inserted is placed after the final one in the array. There is still space for more objects to be added.

When the array reaches its maximum capacity and needs to be recreated with a doubled size

It has reached the maximum capacity of the array, and there are no more spots available. Then it must create a new array that is twice as large. The elements from the previous array should then be copied to the new one, taking O(n) in both conditions (worst and best case).

Amortized time is used to express these two types of time complexity. It allows us to depict the worst-case scenario, which occurs when the internal array reaches its capacity.
However, once it occurs, it will not occur again for a long enough period that the cost will be "amortized." When the maximum capacity of the Array List is reached, the insertion takes O(n) time and for the rest of the cases, it is O(1).

Application of potential method of analysis

When analysing the complexity of Fibonacci heaps, the potential function technique is widely utilized. It is also used in analysing the complexity associated with deletion of element. It takes logarithmic time complexity in this case whereas other operations take constant time. It can also be used to analyse the complexities of splay trees and self-adjusting binary search trees which require logarithmic amortized time per operation.

Common Mistakes

Amortized analysis is a useful tool. It is used with other strategies like average and worst case analysis. In contrast to average-case analysis, amortized analysis does not use probability. In the worst-case scenario, the average performance of each operation is ensured via amortized analysis.

Context and Applications

This topic is critical for the professional exams in both undergraduate and graduate courses, especially for:

• Bachelors of Science in Computer Science
• Masters of Science in Computer Science

Related Concepts

• Potential function algorithm
• Aggregate method for amortized analysis
• Types of amortized analysis

Practice Problems

Q1. In amortized analysis, which of the following methods takes an overcharge for some operations?

1. Aggregate method      
2. Accounting method        
3. Potential method         
4. None

Correct Answer: 2. Accounting method

Explanation- Early in the sequence, the accounting method overcharges some actions, saving the surplus as "prepaid credit" on certain data structure elements

Q2. In amortized analysis, which of the following methods is the most flexible?

1. Aggregate method      
2. None       
3. Potential method         
4. Both (1) and (2)

Correct Answer: 3. Potential method

Explanation- The most flexible potential method because it is defined by computational complexity theory. It's great for calculating a data structure's amortized time and space complexity.

Q3. In amortized analysis, which of the following methods takes different operations with various charges?

1. Aggregate method      
2. Accounting method        
3. Both (1) and (2)     
4. None

Correct answer: 2. Accounting method

Explanation- The accounting approach, rather than aggregate analysis or the prospective method, generally provides a more straightforward picture of an operation's amortized cost.

Q4. In amortized analysis, which of the following methods is used to calculate the overall cost of an algorithm?

1. Aggregate method      
2. Aggregate and potential both
3. None      
4. Potential method    

Correct Answer: 1. Aggregate method

Explanation- The aggregate approach is the first method of amortized analysis, and it entails counting out the complexity of each operation.

Q5. Which of the following methods is used to calculate the potential energy required to fund future operations?

1. Aggregate method      
2. None        
3. Potential method         
4. Accounting method

Correct Answer: 3. Potential method

Explanation- The potential method calculates the potential energy required to fund future operations.