What is Amortized analysis?

Amortized analysis is a technique used to perform micro-level analysis of an algorithm's complexity or resource (time and memory) consumption. It is used for analyzing the time efficiency of data structures that support many operations such as stacks and heaps.
Operations supported by stack include push, pop, multi push, and multi pop while operations supported by heap are inserted, delete, extract-min, and so forth. It focuses on the sequence in which these operations are executed and therefore, provides an accurate cost estimation.

Methods used for amortized analysis

In amortized analysis, it is necessary to know the possible operations because the worst-case operation may modify the state such that the worst-case does not occur for a long period (it amortizes its cost).
Ideally, there are three approaches for amortized analysis:

1. Aggregate analysis: This technique identifies the complexity of each of the possible operations. By calculating the complexity of each operation, one can identify a pattern and calculate the upper bound T(n). The total amortized cost can be calculated as T(n)/ n.
2. Accounting (or Banker's) method: The accounting technique is a type of aggregate analysis. It follows the financial model for amortized analysis. In this method, every operation is allotted a charge called amortized costs. This charge could be higher or lesser than the actual cost. The difference between the amortized and actual cost is called credit. The credit begins at zero and is always positive. If the amortized cost is higher than the actual cost, it can be used to pay for operations that have a lesser amortized cost than the actual cost.
3. Potential method (or potential function method): The potential method is a type of accounting method. The only difference is that this method calculates the credit as the energy that can be used to pay for future operations. It calculates the amortized cost as the sum of the direct cost and the change in potential. The potential may vary with each operation but it should always be positive. This method follows the energy model for amortized analysis.

Amortized analysis for a stack using the aggregate method

To solve a problem using the aggregate method, there are two steps:

• First, prove that the worst-case running time for a sequence of n operations is T(n).
• Next, prove that every operation requires T(n)/n time on average. This means the cost of every operation in the aggregate analysis is the same.

Let there be a stack of size s and the following stack operations.

• Push(s, x): The push operation inserts a new element into the stack. This operation takes O(1) time to push each element.
• Pop(): The pop operation removes the element at the top of the stack. To pop each element, O(1) time is required.
• Multi-pop(k): This operation will pop the top k elements from the stack, and if it gets empty before popping out all the elements, it will stop. The time taken for popping each element in this operation is O(n).

According to aggregate analysis, the time taken to perform each operation is the same. So, for a sequence of n push and pop operations, the total amortized time will be $T\left(n\right)/n = O\left(n\right)/n = O\left(1\right)$ because once an element is pushed to the stack, it can be popped once.

Similarly, for a sequence of n operations, at most n pushes and most n pops can be done. Therefore, for multi-pop, the amortized cost will also be $T\left(n\right)/n = O\left(n\right)/ n = O\left(1\right)$.

Amortized analysis for a stack using the accounting method

In the accounting method, every operation is assigned a charge called amortized cost, distributed amongst the actual cost of the operations and credit.

Consider the stack operations mentioned in the aggregate analysis method.

Here, the actual costs for the stack operations are:

• push - 1
• pop - 1
• multi-pop - min(s,k)

Now, let the amortized cost for each operation be:

• push - 2
• pop - 0
• multi-pop - 0

The objective is to prove that it is possible to use the amortized costs to pay for any sequence of n operations.

Consider the following example to understand this clearly:

Assume a stack of plates in the kitchen. One dollar is paid for the operation when a plate is pushed to the stack, and one dollar credit is left. (Here, one dollar = one unit cost.) This one dollar is placed on the top of the pushed plate as a credit. This means every plate in the stack has a one-dollar credit.

Similarly, one dollar is paid for the operation when the plate is removed (popped) from the stack. For this pop operation, the one-dollar credit will be used. So, the cost of popping will be zero dollars.

Further, multi-pop also performs pop operations as a subroutine. Therefore, the one-dollar credit present on each plate will be used for multi-pop operations. This again means there will be no amortized cost for multi-pop operation.

Hence, the total amortized cost for n push, pop, and multi-pop operations will be O(n), and the average amortized cost for each operation is O(1).

Amortized analysis for a stack using the potential method

The potential method thinks of the work done as the energy that can be used to pay the later operations. It works as follows:

• It begins with a data structure D₀.
• Performs n operations and turns the data structure into D₀, D₁, …, D_n.
• C_i is the cost of every i^th operation, and D_i is the data structure of the i^th operation.
• It is the potential function mapping the D to a number $\varphi$D (the potential of the data structure).

The amortized cost for every i^th operation can be denoted as:

$a_i = c_i + \varphi D_i - \varphi D_{(i-1)}$

Therefore, the total amortized cost is:

$\sum _{i=1}^n{a}_i =\sum _{i=1}^n(c_i + \varphi D_i - \varphi D_{(i-1)})$

Consider the stack operations mentioned in the aggregate analysis method.

The potential for the stack is the number of objects in the stack.

Therefore, $\varphi D_0 and \varphi D_i \ge 0.$

The amortized cost for the operations will be:

• push 
  • Potential change = $\varphi D_i - \phi D_{(i-1)} = (s + 1) - s = 1.$
  • Amortized cost = $c_i’ = c_i + \varphi D_i - \varphi D_{(i-1)} = 1 + 1 = 2.$
• pop 
  • Potential change = $\varphi D_i - \varphi D_{(i-1)} = (s - 1) - s = -1.$
  • Amortized cost = $c_i’ = c_i + \varphi D_i - \varphi D_{(i-1)} = 1 + (-1) = 0.$
• multi-pop(s, k)  = k^’ = min(s, k)
  • Potential change =$\varphi D_i - \varphi D_{(i-1)} = -k’$
  • Amortized cost = $c_i’ = c_i + \varphi D_{i }- \varphi D_{(i-1)} = k’ + (-k’) = 0.$

Therefore, the amortized cost for each operation will be O(1), and the total amortized cost for n operations will be O(n).

Context and Applications

Amortized analysis is a topic in data structure subject in Computer Science. It is studied in courses such as:

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

Practice Problems

Q1. Which of the following factors is considered while analyzing an algorithm?

1. Resources used for the execution
2. Cost of the operation
3. Type of the operation
4. None of the above

Answer: Option a

Explanation: To analyze an algorithm is to check the sequence of operations and the resources such as memory or time is consumed while executing the operation.

Q2. Amortized analysis is used in which of these algorithms?

1. Hash tables
2. The actual cost of cryptography
3. Algorithms calculating the actual cost of an operation
4. The total amortized cost of the operation

Answer: Option a

Explanation: Amortized analysis is used in various data structures including hash tables.

Q3. Which method follows a financial model to perform the amortized analysis?

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

Answer: Option a

Explanation: In the data structure, the accounting (banking) method follows the financial model for amortized analysis.

Q4. Which method follows an energy model to perform the amortized analysis?

1. Accounting method
2. Potential function method
3. Asymptotic method
4. Aggregate method

Answer: Option b

Explanation: The potential function method follows an energy model for amortized analysis.

Q5. Which of the following methods is not a method used for amortized analysis?

1. Accounting method
2. Potential function method
3. Sorting method
4. Aggregate method

Answer: Option c

Explanation: Amortized analysis can be done using the accounting method, aggregate method, and potential method.

Common Mistakes

In data structures, two techniques, asymptotic analysis, and amortized analysis are used to find the runtime performance of an algorithm. However, it is essential to note that both methods are different. An algorithm's worst case, best case, and average-case time complexity are determined with the asymptotic analysis. Contrarily, the amortized analysis involves analysis of the sequence of operations which ensures that the worst-case average time is lesser than the worst-case time of a specific operation.

Related Concepts

• Sorting algorithms
• Space complexity
• Queue, stack, and array in data structure
• Graphs in data structure