1. How many cost units are spent in the entire process of performing 40 consecut
ID: 3714141 • Letter: 1
Question
1. How many cost units are spent in the entire process of performing 40 consecutive push operations on an empty array which starts out at capacity 8, assuming that the array will double in capacity each time a new item is added to an already full dynamic array? As N (ie. the number of pushes) grows large, under this strategy for resizing, what is the average big-oh complexity for a push?
2. How many cost units are spent in the entire process of performing 40 consecutive push operations on an empty array which starts out at capacity 8, 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 (ie. the number of pushes) grows large, under this strategy for resizing, what is the average big-oh complexity for a push?
Explanation / Answer
SOLUTION:-
(1):- Total Array will be as per amortized method i.e (8+16+32+64)=120 but we will end on 40 so we will consider the array only for 8+16+32+40 for 40 consecutive push operations and it will cost 96 and the average big-oh complexity for a push is O(1)+
(2):- Total Array will be as per amortized method i.e 8+10+12+14+16+18+20+22+24+26+28+30+32+34+36+38+40 for 40 consecutive push operations and it will cost 408 and the average big-oh complexity for a push is O(n).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.