Solution Set 5

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.

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 and two which aren't a power of k.

Operations power of k

We'll ignore the first operations as a power of k even though k⁰=1. The cost in our example is thus 2 + 4 + 8 = 14. The first question we need to answer is that given n operations, how many of those operations will be powers of k. The answer is k raised to what power would equal n? And as we have seen earlier, it is log_kn. Let's plug in the values for our example and see if the answer matches what we expect.

$$log_28 = 3$$ ...