Consider an implementation of a stack using an extendible array. That is, instea

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.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.