Consider an implementation of a stack using an extendible array. That is, instea
ID: 3667380 • Letter: C
Question
Consider an implementation of a stack using an extendible array. That is, instead of giving up with a "StackFullException" when the stack becomes full, we replace the current array S of size N with a larger one of size f(N) and continue processing the push operations. Suppose that we are given two possible choices to increase the size of the array: (l)f(N) = N + c (for convenience, we start with an initial array of size 0) (2) f(N) = 2N (we start with an initial array of size 1). Compare the two strategies and decide which one is better. To analyses the two choices, assume the following cost model: A "regular" push operation costs one unit of time. A "special" push operation, when the current stack is full, costs f(N) + N + 1 units of time. That is, we assume a cost of f(N) units to create the new array, N units of time to copy the N elements and one unit of time to copy the new element.
Explanation / Answer
Both array expasion strategies are good in their own ways. According to the actual scenario only, we can decide whether to go for the N+C strategy or 2N strategy. If the scenario is that we have an idea of about how many elements will be added more, then will go for N+C strategy, ie, will increase the size by capacity we forsee. But if there is no idea about how many elements more will be added, then we can go for 2N strategy.
There is no strategy which we can say as best, unless the scenario is given.