Recall the “automatic resizing” strategy used in our array-based stack implement
ID: 3675371 • 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 2X 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 (n).
Explanation / Answer
T(n) = T(n/2) + n
Whenever a resizing occurs at capacity n/2 to n , the time taken to push already existing n/2 elements in the stack is n/2 * O(1) = O(n/2).
Now, n/2 more elements can be pushed. Hence , tine taken will be n/2 +n/2 = O(n).
Now, consider the time for the current n/2 push operations . It will be , T(n/2).
Hence the recursive formula will be :
T(n) = T(n/2) + n
Thus T(n) O(n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.