Consider an implementation of a stack using an extendible array. That is, instea
ID: 3667498 • 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
In case of Regular push operation, each element requires cost of one unit. So, if we have n numbers of element to be pushed on the stack it will increase the cost of push as
1 + 2 + 3 + ....... + n = n(n+1) /2.
That is a amortize cost of n(n+1)/2 per element. Thus it it not good but
In case of Special Push operation we increase the size of array as 2N i.e. double the size. cost will be f(n)+N+1
Now, in any sequence of n operations, the total cost for resizing is 1 + 2 + 4 + 8 +. . .+ 2i for some 2i< n (if all operations are pushes then 2i will be the largest power of 2 less than n). This sum is at most 2n1.
In comparson Special Push operation is better because it requires less cost per element as compared to regular push operation.