Suppose that a dynamic array stack doubles its capacity

Question

1. How many cost units are spent in the entire process of performing 32 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 big-oh complexity for a push?

2. How many cost units are spent in the entire process of performing 32 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 big-oh complexity for a 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.)

 

 

Answer 1

The queries of mathematics are descriptive as above. Write the whole solution of every question smartly. 1. How many cost units are spent in the complete procedure of performing 32 consecutive push operations on an empty array that begins 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 (for instance the number of pushes) produces huge, under this tactic for resizing, what is the big-oh complexity for a push? 2. How many cost units are spent in the entire procedure of performing 32 consecutive push operations on an empty array that begins out at capacity 8, assuming that the array will produce via a constant 2 spaces each time a new item is added to an already full dynamic array?