1. How many cost units are spent in the entire process of performing 16 consecut
ID: 3662977 • Letter: 1
Question
1. How many cost units are spent in the entire process of performing 16 consecutive push operations on an empty array which starts out at capacity 8, assuming that the array will double in capacity each time new item is added to an already full dynamic array? Now try it for 32 consecutive push operations. As N (ie. the number of pushes) grows large, under this strategy for resizing, what is the big-oh complexity for push?
2. How many cost units are spent in the entire process of performing 16 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 new item is added to an already full dynamic array? Now try it for 32 consecutive push operations. As N (ie. the number of pushes) grows large, under this strategy for resizing, what is the big-oh complexity for push?
3. Suppose that a dynamic array stack doubles its capacity when it is full, and shrinks (on Pop only) its capacity by half when the array is half full or less. Can you devise a sequence of N push() and pop() operations which will result in poor performance (O(N^2) total cost)? How might you adjust the array's shrinking policy to avoid this? (Hint: You may assume that the initial capacity of the array is N/2.)
Explanation / Answer
1)
56 Cost Units
O(1)+
2)
260 Cost Units
O(n)
3)
8 items 8 double to 16 0 copy 8 + 8 16 double to 32 0 copy 16 + 16 3256 Cost Units
O(1)+
2)
8 items 8 add 2, make 10 0 copy 8 add 2 10 add 2, make 12 0 copy 10, add 2 12 add 2, make 14 0 copy 12, add 2 14 add 2, make 16 0 copy 14, add 2 16 add 2, make 18 0 copy 16, add 2 18 add 2, make 20 0 copy 18, add 2 20 add 2, make 22 0 copy 20, add 2 22 add 2, make 24 0 copy 22, add 2 24 add 2, make 26 0 copy 24, add 2 26 add 2, make 28 0 copy 26, add 2 28 add 2, make 30 0 copy 28, add 2 30 add 2, make 32 0 copy 30, add 2 32260 Cost Units
O(n)
3)
Push values onto the stack until you reach capacity, so that the capacity doubles. Then, pop a value from the stack, which will cause the size to drop below half of the capacity, which in turn will cause the capacity to be cut in half. To avoid this, I would change the array's shrinking policy to be: Shrink capacity by half when the array is 1/4 full or less.Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.