Solution Set 5
Explore amortized analysis by calculating the average cost per operation across a series of algorithmic actions. Understand how to handle costs when operations vary, such as those dependent on powers of a base number k, and apply the accounting method to dynamic array insertion. This lesson helps you grasp how amortized cost offers insight into overall algorithm efficiency beyond individual steps.
We'll cover the following...
Solution 1
The question asks us to work out the amortized cost of each operation for a total of n operations. An operation costs i if it is a power of k and costs 1 if it isn't a power of k.
For simplicity let's assume k = 2 and the total number of operations is a power of k. Let the total number of operations be 8. The operations and their cost is shown below.
| Operation Number | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Cost | 1 | 2 | 1 | 4 | 1 | 1 | 1 | 8 |
In the above table, operation# 2, 4 and 8 are powers of k = 2 and are shown in blue. We need to calculate the total cost of all the operations and then divide it by n to get the amortized cost per operation.
We'll to compute two costs to get the total cost of n operations. One operations which are a power of k = 2 ...