4. (20 points) Recall that we investigated in studio the asymptotic complexity o

Question

4. (20 points) Recall that we investigated in studio the asymptotic complexity of im plementing a list using an array. When the array became full, we tried at least the following two strategies to accommodate the new elements given that the array was already full: . Allocate a new array whose size is exactly one slot bigger than the old, full array . Allocate a new array whose size is twice the size of the old, full array For either approach, assume that the size of the very first (initial) array is 1, and you (a) (6 points) Recalling our work from studio, what expression represents the total i. (3 points) the new array's size is just one element bigger than the old, full can assume that n below is a power of 2. work done to insert n elements into the array list, when arr ii. (3 points) the new array's size is twice the size of the old, full array: e- ) (b) (14 points) Now suppose we are going to the oppposite of what we did in studio. Instead of creating newer larger arrays to accommodate more elements in our array-based list, we are going to remove elements from the array, and replace a larger, less full array with a smaller, full one. We do this by n delete operations on our array-based list that, from the perspective of this problem, initially contained n elements, and we study two scenarios; i. (7 points) When an element is deleted, we replace the old array by one with exactly one fewer element. As with problem 3, that involves allocating a new array, and copying some elements from the old array into the new one. Below develop a summation expression T(n) for the amount of time needed to delete n elemnts from the array-based list that initially contained n elements. Your answer below must explicitly show the asymptotic work performed by each call to delete, as the list goes from n to 0 elements. After developing that expression, state its closed form using (-..) notation. CSE 247 (Exam I) 7- Due by End of sessiorn ii. (7 points) When an element is deleted, we see if the current array is half full. If so, we allocate the newer, smaller array to be half the original array's size, and copy over the elements as above. As before, develop T(n) as the summation expression for the work performed to go from n (a power of 2) to 0 elements, and state its closed form solution using (--) notation.

Explanation / Answer

a)
1.
For inserting n elements, when array size will grow by one in each iteration:
At start array size is 1, Hence while inserting next element, we will create an array of size 2 and copy the first element... Again, create an array of size 3 and copy starting 2 elements..
So for n elements, the effort will be:
1 + 2 + 3 + .. (n-1)

If we notice carefully, they will be equal to n(n-1)/2
Hence the assymptotic coplexity is of order n^2.

2. When the new array size is doubled everytime,
We will start with 1 element, and create a new array of size 2, Once size 2 array is filled, we will create the array with size 4, then size 8... and so on..

When we create size 2 array, we need to copy 1 element from older array. When we create size 4 array, we need to copy 2 elements from older array and so on..

So total effort = 1 + 2 + 4 + 8 + ... + log(n) terms

If we notice carefullt, it is nothing but of order log(n) only..

b)
1. So for n elements array, if we delete one element, we need to copy (n-1) elements to the new array.. Then (n-2) elements and so on
T(N) = T(N-1) + c
Total effort: (n-1) + (n-2) + .. + 2 + 1
Overall complexity: of order n^2

2. For n elements, once we delete n/2 elements, then only we crete a new array...
Hence n/2 + n/4 + ... + 1 (logN terms)
Overall complexity: of order log(N)

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.