Question

3. Suppose we are doing a sequence of operations (numbered 1, 2,3, ..) such that the ith operation: costs 1 if i is not a power of 2 costs i if i is a power of 2. For example, the following table shows the costs for each of the first few operations Operation1 4 4 2 Cosi Determine the best amortized 00 for this operation, using both the aggregate method and the accounting method.

3. Suppose we are doing a sequence of operations (numbered 1, 2, 3, ...) such that the ith

operation:

- costs 1 if i is not a power of 2

- costs i if i is a power of 2.

For example, the following table shows the costs for each of the first few operations:

Operation 1 2 3 4 5 6 7 8 9 …

Cost 1 2 1 4 1 1 1 8 1 …

Determine the best amortized O() for this operation, using both the aggregate method and the accountig method.

Answer 1

what is amortised cost using aggregate method is

amortized cost = total cost of n operation / n

so we have to just find the cost of all the operations and then add them and divide them by n

so total cost = 1+ 2+ 1 + 4 + 1 + 1 + 1+ 8 ...   

n + it will approx to 3n

log(n-1)) 2'

which is equivalent to O(n)

so amortized cost = O(n) / n = O( 1)  

2.) accounting method tells that we store some cost for the cheaper actions and then use that extra cost for the heavy actions.

suppose we make a cost of 3 for every operation so what happen now look at following table

operation	available cost	remaining cost
1	3	3 -1 =2
2	2 + 3= 5	5 -2 =3
3	3+3= 6	6-1 =5
4	5+3 =8	8-4 =4
5	4+3 =7	7-1=6
6	6+3 =9	9-1 =8
7	8+3 =11	11-1 =10
8	10+3 =13	13-8=5

as we can see that the cost 3 is sufficient to complete the operations and it will satisfy all the requirements.

so for the n operations total cost will be 3*n  

so for one operation cost is 3 which is equivalent to O(1)

I hope this will help you so please give positive ratings :)))