Question

Consider the append() operation for a Dynamic Array. In the best case, the operation is O(1). This corresponds to the case where there was room in the space we have already allocated for the array. However, in the worst case, this operation slows down to O(n). This corresponds to the case where the allocated space was full and we must copy each element of the array into a new (larger) array. This problem is designed to discover runtime bounds on the average case when various array expansion strategies are used, but first some information on how to perform an amortized analysis is necessary.

1. Each time an item is added to the array without requiring reallocation, count 1 unit of cost. This cost will cover the assignment which actually puts the item in the array.

2. 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 4 spaces and is holding 3 items, adding the forth will cost 1. However, if the array has 4 spaces and is holding 4 items, adding the fifth will cost 5 (4 to move the existing items + 1 to assign the fifth 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 execution time.

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 40 consecutive append operations on an empty array which starts out at capacity 4, assuming that the array will double in capacity each time a new item is added to an already full dynamic array? As N (i.e., the number of appends) grows large, under this strategy for resizing, what is the average big-O complexity for an append?

2. How many cost units are spent in the entire process of performing 40 consecutive append operations on an empty array which starts out at capacity 4, assuming that the array will grow by a constant 2 spaces each time a new item is added to an already full dynamic array? As N (i.e., the number of appends) grows large, under this strategy for resizing, what is the average complexity for an append?

Answer 1

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)