Amortized analysis is a technique used to determine the average time complexity of an algorithm over a series of operations. It is a way to analyze the performance of data structures and algorithms that have a high variance in the time complexity of individual operations.
In traditional worst-case analysis, we determine the time complexity of the worst-case operation. This means that if there are n operations, the time complexity could be O(n2), even if most operations are much faster than that. Amortized analysis, on the other hand, looks at the average time complexity over a series of operations. This means that the time complexity of an individual operation could be higher or lower than the average, but the average time complexity over a series of operations will be more accurate.
There are three common methods of amortized analysis: aggregate analysis, accounting method, and potential method.
Aggregate analysis: In aggregate analysis, we analyze the total cost of a series of operations and divide it by the number of operations to get the average cost. For example, let’s consider a dynamic array that doubles in size when it runs out of space. The cost of adding an element to the array is O(1) on average. However, the cost of doubling the array is O(n), where n is the size of the array before the doubling. If we perform n operations, the total cost is O(n2) in the worst-case scenario. However, if we use aggregate analysis, we can see that the total cost of n operations is O(n), which gives us an average cost of O(1).
Accounting method: In the accounting method, we assign a "charge" to each operation, which is greater than the actual cost of the operation. We then use this extra charge to pay for future operations. For example, let’s consider a stack that uses an array to store elements. When the stack becomes full, we allocate a new array that is twice the size of the previous array. The cost of pushing an element onto the stack is O(1) on average. However, when we allocate a new array, we charge each push operation an extra O(1) to pay for the cost of the reallocation. We can show that the total charge is O(n) for n push operations. Therefore, the average cost of a push operation is O(1).
Potential method: In the potential method, we assign a "potential" to the data structure before and after each operation. The potential is a value that represents the extra cost of the current data structure compared to the best-case scenario. For example, let’s consider a binary counter that increments a number represented as an array of bits. The cost of incrementing the counter is O(1) on average. However, we can use the potential method to show that the worst-case cost is O(log n). We assign a potential of 2k to each bit position that changes from 0 to 1. We can show that the potential of the counter is at most 2n, where n is the number of bits in the counter. Therefore, the average cost of an increment operation is O(1) because the extra cost is paid for by the potential.
In conclusion, amortized analysis is a powerful technique for analyzing the average time complexity of algorithms over a series of operations. It can be used to provide more accurate estimates of the performance of data structures and algorithms than traditional worst-case analysis.