4. A dynamic array is a data structure that can support an arbitrary number of append...

 

Transcribed Image Text:

4. A dynamic array is a data structure that can support an arbitrary number of append (add to the end) operations by allocating additional memory when the array becomes full. The standard process is to double (adds n more space) the size of the array each time it becomes full. You cannot assume that this additional space is available in the same block of memory as the original array, so the dynamic array must be copied into a new array of larger size. Here we consider what happens when we modify this process. The operations that the dynamic array supports are Indexing A[i]: returns the i-th element in the array Append (A,x): appends x to the end of the array. If the array had n elements in it (and we are using 0-based indexing), then after Append(A, x), we have that A [n] is x. (a) Derive the amortized runtime of Append for a dynamic array that adds n/2 more space when it becomes full. (b) Derive the amortized runtime of Append for a dynamic array that adds n more space when it becomes full. (c) Derive the amortized runtime of Append for a dynamic array that adds some constant C amount of space when it becomes full. 4. A dynamic array is a data structure that can support an arbitrary number of append (add to the end) operations by allocating additional memory when the array becomes full. The standard process is to double (adds n more space) the size of the array each time it becomes full. You cannot assume that this additional space is available in the same block of memory as the original array, so the dynamic array must be copied into a new array of larger size. Here we consider what happens when we modify this process. The operations that the dynamic array supports are Indexing A[i]: returns the i-th element in the array Append (A,x): appends x to the end of the array. If the array had n elements in it (and we are using 0-based indexing), then after Append(A, x), we have that A [n] is x. (a) Derive the amortized runtime of Append for a dynamic array that adds n/2 more space when it becomes full. (b) Derive the amortized runtime of Append for a dynamic array that adds n more space when it becomes full. (c) Derive the amortized runtime of Append for a dynamic array that adds some constant C amount of space when it becomes full.