Question

Dynamic Arrays Revisited (40 points) A dynamically re-sizing array is an array that is initially allocated at size 1. and every time you need to insert past the end of the array you double its size and copy elements from the old array to the new array. In class, we showed that n inserts into a dynamic array can be accomplished in O(n) using an accounting argument where we pre-paid $3 for each insert, thus pre-paying for its doubling and the doubling of one older element. (a) Formally write the proof for this accounting (b) Show the same bound using the potential method (c) Does this O(n) bound on n operations hold if you include deletions? Why or why not?

please explain. Thanks in advance

Answer 1

Dynamically resizing Array 1. Accounting method Ci-Actual cost of a operation i ci - Amortizech Cost For any Sequence of u operations, - izl Amortized Cost should always ley be less. For insert, we assign $3 and its altual cost is a lf array has space otherwise n+1. since, we have to copy n elements. For any Seauence of u insert operatias Amortized cost is $3n and actual cost is 1+(1+1)+(2+1)+1+(4+1)+1+1+...+1+(841)+-- = m*1+ 2+2te.stellen) lognt! 2n + 2 -1 = n 2n-1 = 3n-1 21 <3n Scanned with CamScanner

2. Potentiat method Let us define Potential fonction o on data structure as number of element. o cool=0. As we seed earlier, actreat cost is on-1, we can calculate, Tamortized = Tacticant ($Csi) – ºcsi-) *C Os operation ci constart = 1 + 2 (i - (-11) For n operation, amortized cost is $3n. which is a actual cost (7) greater than CS Scanned with CamScanner

I 3. If we lucleede deletions, it wont cock. for Example, we have following sequence of operations delete insest delete insed .. Insert, insert ...., Insest Them. It 1. ntimes ineesta.. Paces matinan 1 . a next delete ist n insertion For I insert on an ang each operation takes ocm) time. Scanned with CamScanner