How can you use amortized analysis to determine the cost of operations?

1 Aggregate analysis

Aggregate analysis is the simplest form of amortized analysis. It involves adding up the total cost of all the operations in a sequence and dividing it by the number of operations. This gives you the average cost per operation, which is the amortized cost. For example, suppose you have an algorithm that appends an element to a dynamic array. If the array is full, you need to allocate a new array with twice the size and copy all the elements over. This is an expensive operation that occurs every time the array size is a power of two. However, you can show that the amortized cost of appending an element is O(1) by using aggregate analysis. The total cost of n append operations is O(n) plus the cost of copying, which is O(n) in the worst case. Therefore, the average cost per operation is O(2n/n) = O(1).

2 Accounting method

Accounting method is another form of amortized analysis that assigns different charges to different operations based on their actual and amortized costs. The idea is to use some operations to pay for the extra cost of other operations. For example, suppose you have a stack that supports two operations: push and pop. Push adds an element to the top of the stack, and pop removes and returns the top element. However, every 10th pop operation also prints the entire stack. Printing the stack is an expensive operation that costs O(n), where n is the number of elements in the stack. How can you determine the amortized cost of pop? One way is to use accounting method and assign a charge of 1 to push and pop, and a charge of n to print. However, this would result in a deficit of O(n) every 10th pop. To avoid this, you can overcharge push by 2 instead of 1, and store the extra charge as a credit on each element. This way, every 10th pop can use the credits from the previous 9 pops to pay for printing. Therefore, the amortized cost of pop is O(1).

3 Potential method

Potential method is a more general form of amortized analysis that uses a potential function to measure the difference between the actual and amortized costs of operations. The potential function assigns a numerical value to the state of the data structure or the algorithm, based on some criteria. The amortized cost of an operation is then defined as the actual cost plus the change in potential. The idea is to choose a potential function that captures the variation in the cost of operations over time. For example, suppose you have a binary counter that supports two operations: increment and decrement. Increment adds one to the counter, and decrement subtracts one. Both operations are implemented by flipping bits in the counter, starting from the least significant bit. Flipping a bit from 0 to 1 costs 1, and flipping a bit from 1 to 0 costs 0. How can you determine the amortized cost of increment? One way is to use potential method and define the potential function as the number of 1 bits in the counter. The actual cost of increment is the number of bits flipped, which is at most O(log n), where n is the value of the counter. The change in potential is the difference between the number of 1 bits before and after increment, which is at most 1. Therefore, the amortized cost of increment is O(log n) + 1 = O(log n).

4 Here’s what else to consider

This is a space to share examples, stories, or insights that don’t fit into any of the previous sections. What else would you like to add?