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.

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 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$$

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 log_kn + 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 k^x+1 - 1. We can test it on our example.

$$2^{3+1}-1 = 2^4-1=15 = 1+2+4+8$$

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 log_kn such operations and their sum is represented by

$$k^{(number\:of\:operations\:that\:are\:power\:of\:k+1)} -1 -1$$

$$=k^{(log_kn+1)}-2$$

Operations not power of k

We have already calculated the number of operations that are power of k among the total n operations, which is log_kn so the number of operations not power of k are n - log_kn.

Total Cost

The total cost is thus the sum of costs of operations that are power of k and those that are not power of k.

$$Total\:Cost=Cost\:of\:operations\:power\:of\:k+Cost\:of\:operations\:not\:power\:of\:k$$

$$Total\:Cost=(k^{(log_kn+1)}-2)+1*(n-log_kn)$$

$$Total\:Cost=((k^{log_kn}*k)-2)+(n-log_kn)$$

$$Total\:Cost=((n*k)-2)+(n-log_kn)$$

$$Total\:Cost=nk-2+n-log_kn$$

We can plug in values for n and k from our example to verify that our expression correctly computes the total cost.

$$Total\:Cost=nk-2+n-log_kn$$

$$Total\:Cost=8*2-2+8-log_28$$

$$Total\:Cost=16-2+8-3$$

$$Total\:Cost=19$$

Amortized Cost

To get the amortized cost we'll simply divide the total cost by the total number of operations which is n.

$$Amortized\:Cost=\frac{nk-2+n-log_kn}{n}$$

$$Amortized\:Cost=\frac{nk}{n}+\frac{n}{n}-\frac{log_kn}{n}-\frac{2}{n}$$

$$Amortized\:Cost=k+1-\frac{log_kn}{n}-\frac{2}{n}$$

As n becomes larger and larger ²⁄_n becomes 0. Similarly as n increases the term ^log_kn⁄_n also tends to zero because the denominators increases faster than the numerator. Finally, we can ignore the constant term 1 and are left with only k. Hence the amortized cost of each operation is thus O(k).