***Please answer/explain all the questions and use Phthon 3 if necessary.Thank y
ID: 3746480 • Letter: #
Question
***Please answer/explain all the questions and use Phthon 3 if necessary.Thank you in advance and will rate you***
1.Recall how lists are implemented using arrays: A list of length occupies the
lowest indices of an array that’s allocated to be bigger than necessary. As long as there’s
1 more room in the array, an append takes O(1) time by simply storing to the next available
location (the index of which is kept in an auxiliary variable). When the array becomes full, a
new array that’s twice as big is allocated, and everything is copied to it (and the old array is
garbage collected), taking time O(current length of list). In class we calculated that starting
with an empty list, n appends still take O(n) time even though not every append is O(1).
Now suppose we start with a list of length n and repeatedly delete the last element. Since
the array doesn’t need to be resized (only the variable holding the last available index is
decremented), each delete takes O(1) time. However, we may deem that wasteful in terms of
memory space, since a very small list could end up occupying a large chunk of memory. To
fix that, suppose that whenever the array hits “half capacity” (i.e., deletion results in the list
having half the size of the array), we create a new array of half the size (“just big enough”)
and copy the contents over, taking time O(current length of list). Space is saved since the
old (bigger) array is garbage collected.
a. Show that the sequence of n deletions still takes O(n) time.
b. Supposing we allow both appends and deletions of the last element, show that
it’s possible for a sequence of n operations, starting from an empty list, to take (n2)
time. (Thus, real implementations actually use different thresholds for the “growing”
and “shrinking” steps.)
Explanation / Answer
Answer:
a. Show that the sequence of n deletions still takes O(n) time.
As per the given data length of the initial array is N
As same as like insertion, deleting from end of the list happens in constant time O(1) as long as we storing the last index.
Let the cost of 1 delete operation be c, therefore for n elements, cost of deleting would nc
As per the rules of azmortized analysis, if we drop the constant, it will be order O(n) for deletion as well.
Now, we have a reduce mechanism which shrinks the size of array by half by creating a new array of half the size and then assigning each value of 1st array to the 2nd array.
Let the cost of assigning one element to new array be d, therefore the cost of assigning n/2 elements
(since we only reduce when the array is half the size of allocated size) will be (n x d)/2
Since we only have to reduce the array size by half and copy the elements, the next time we have to
reduce the size at n/4, so cost of reduce will be (n x d)/4
Therefore the cost of reduction whenever it happens will be n x ( d/2 + d/4 + d/8 + d/16 + ......)
Now the total time complexity of deletion = time complexity of deleting n elements + reduction whenever needed.
= nc + n x ( d/2 + d/4 + d/8 + d/16 + ......)
= n x (c + d/2 + d/4 + d/8 + d/16 + .......) { where c = cost of 1 delete operation & d = cost of 1 copy
operation)
Since (c + d/2 + d/4 + d/8 + d/16 + .......) is a constant, time complexity for deletion will be O(n).
b. Supposing we allow both appends and deletions of the last element, show that it’s possible for a sequence of n operations, starting from an empty list, to take (n2) time. (Thus, real implementations actually use different thresholds for the “growing” and “shrinking” steps.)
Initially it will be a zero size and consider the worst case of inserting k/2 elements at once and then
deleting all those k/2 elements at once (without any inserts). This case will exploit maximum array size
expansions and deletions.
Time complexity = insertion for k/2 elements + resize time for expanisions + deletion for k/2 elements +
resize time for deletions.
Since we've already seen that insertion and deletion complexities it will k + c for insertion and k + d for
deletion.
= k + c + k + d { where c & d are constant parts for insertion and deletion time complexities }
= (2k) where k = total no of elements inserted and deleted.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.