Recall the \"automatic resizing\" strategy used in our array-based stack impleme
ID: 3674662 • Letter: R
Question
Recall the "automatic resizing" strategy used in our array-based stack implementation and probably in your Service Queue solution. Let's assume the following framework for the stack: The array capacity is initially some constant. For simplicity, let's make it 2. When the array is at capacity and the push operation is called, a new array is allocated with 2% the capacity of the current buffer. Necessary copying from the old array to the new happens at this time. YOUR JOB: Prove that the total time taken by a sequence of n push operations is Theta(n).Explanation / Answer
Every time when a resize is required, the n/2 element needed to be copied and new n/2 elements can be entered. Total of n push operations. Now, cosidering the time taken till n/2 size.
Hence , T(n) = T(n/2) + n
T(n) (n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.