Solution Set 5
Solutions to problem set 4
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 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 k0=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 logkn. Let's plug in the values for our example and see if the answer matches what we expect.
This is exactly what we see in our example, 2, 4 and 8 appear as powers of k = 2. Note, if we were counting the first operation as a power of 2 then we would have logkn + 1 powers of k occurring in n operations.
Next, we need to find out what these operations would sum to.You can deduce by inspection or if you are mathematically adept would already know that the sum of the first x powers of k is kx+1 - 1. We can test it on our example.
As you can see that this includes 1 as a power of k so we will need subtract an additional 1 for our example.
So now we can calculate the sum of all the operations in n operations that are powers of k. There will be logkn such operations and their sum is represented by
...