Question

Each time an item is added and requires reallocation, count X + 1 units of cost, where X is the number of items currently in the array. This cost will cover the X assignments which are necessary to copy the contents of the full array into a new (larger) array, and the additional assignment to put the item which did not fit originally To make this more concrete, if the array has 8 spaces and is holding 5 items, adding the sixth will cost 1. However, if the array has 8 spaces and is holding 8 items, adding the ninth will cost 9 (8 to move the existing items + 1 to assign the ninth item once space is available).

When we can bound an average cost of an operation in this fashion, but not bound the worst case execution time, we call it amortized constant execution time, or average execution time. Amortized constant execution time is often written as O(1+), the plus sign indicating it is not a guaranteed execution time bound.

In a file called amortizedAnalysis.txt, please provide answers to the following questions:


1. How many cost units are spent in the entire process of performing 16 consecutive push operations on an empty array which starts out at capacity 8, assuming that the array will double in capacity each time new item is added to an already full dynamic array? Now try it for 32 consecutive push operations. As N (ie. the number of pushes) grows large, under this strategy for resizing, what is the big-oh complexity for push?


2. How many cost units are spent in the entire process of performing 16 consecutive push operations on an empty array which starts out at capacity 8, assuming that the array will grow by a constant 2 spaces each time new item is added to an already full dynamic array? Now try it for 32 consecutive push operations. As N (ie. the number of pushes) grows large, under this strategy for resizing, what is the big-oh complexity for push?

Answer 1

1. Average of total Cost = Total Cost/n = O(1)

2. Average of total Cost = Total Cost/n = O(n)

Step-by-step explanation:

1) Array has Initial size of 8

For adding 16 elements

1. So Cost for first 8 element its 8.

2. On adding 9th element cost is (8+1) = 9 and array is resized to size of 16

3. Then for 10th,11th,12th,.......,16th element Cost is 7.

So total cost is 8 +9 + 7 = 24 ..So for adding 16 elements Cost is 24 units.

For adding 32 elements

1. So Cost for first 8 element its 8.

2. On adding 9th element cost is (8+1) = 9 and array is resized to size of 16

3. Then for 10th,11th,12th,.......,16th element total Cost is 7.

4. On adding 17th element cost is (16+1) = 17 and array is resized to size of 32.

5. Then for 18th,19th,20th,.......,32th element total Cost is 15.

So total cost is 8 +9 + 7 +17+15= 56 ..So for adding 32 elements Cost is 56 units.

We are Intrested in finding the Amortized Cost i.e Averga cost over large number of insertion:-

When the array size is doubled:-

N operation of N pushes will have cost of 1+2+4+8+16+.. + 2k where 2k < N, Summing upo the series we have

2k-1 - 2 . But 2k <=n <= 2k-1 So,

The total cost of the sequence of n insertions will be O(n) .

Since the Amortized Cost is the Average of total Cost = Total Cost/n = O(1)

2) resize by increasing the size by 2 elements

For adding 16 elements

1. So Cost for first 8 element its 8.

2. On adding 9th element cost is (8+1) = 9 and array is resized to size of 10

3. Then for 10th element Cost is 1

4. Then for 11th element Cost is 11

5.Then for 12th element Cost is 1

6.Then for 13th element Cost is 13

6.Then for 14th element Cost is 1

6.Then for 15th element Cost is 15

6.Then for 16th element Cost is 1

So total cost is 60 ..So for adding 16 elements Cost is 60 units.

For adding 32 elements

1. So Cost for first 8 element its 8.

2. On adding 9th element cost is (8+1) = 9 and array is resized to size of 10

3. Then for 10th element Cost is 1

4. Then for 11th element Cost is 11

5.Then for 12th element Cost is 1

7.Then for 13th element Cost is 13

8.Then for 14th element Cost is 1

9.Then for 15th element Cost is 15

10.Then for 16th element Cost is 1

11. Then for 17th element Cost is 17

12. Then for 18th element Cost is 1

13.Then for 19th element Cost is 19

14.Then for 20th element Cost is 1

15.Then for 21th element Cost is 21

16.Then for 22th element Cost is 1

17.Then for 23th element Cost is 23 .. . . .. .. Then for 31th element Cost is 31 .. . . . . . . . . .. Then for 32th element Cost is 1 .

So total cost is 260 ..So for adding 32 elements Cost is 260 units.

N operation of N pushes will have cost of 1+2+3+4+5+.. + N-1 = N(N-1)/2

The total cost of the sequence of n insertions will be O(n2) .

Since the Amortized Cost is the Average of total Cost = Total Cost/n = O(n)