Please answer in detail Suppose that we have a stack whose size is not allowed t
ID: 3842180 • Letter: P
Question
Please answer in detail
Suppose that we have a stack whose size is not allowed to exceed K (for instance, if K 10, then we are not allowed to have more than 10 elements on the stack at any time). If you try to Push an element onto a stack that is already full, then nothing happens. Suppose that after every K operations, we automatically make a copy of the stack for back-up purposes. (Note the stack may or may not be full at this point.) Suppose that Push and Pop each cost $1 (including if you try to Push an element onto an already-full stack). Suppose that copying the stack costs SC, where C is the number of elements currently on the stack. Perform an amortized analysis of the running time of n operations. State your answer in terms of the average cost per operation, in dollars (that is, do not use big-O notation).
Explanation / Answer
Amortized analysis of the running time of n operations is to analyze the sequence of operations to show that the average of operation is small even though performing one operation may be expensive. Its the average performace in worst case.
So in this scenario, we have a stack of size K (K=10), and performing K operations (push/pop) leaves the stack filled with C elements (C<=K). Then for performing (K+1)th operation, we have total cost incurred:
(K+C+1) .Additonal 1 is for (K+1)th push/pop operation performed on the stack.
-One thing to nore that if the stack is full then even if new element is pushed, the contents are going to be same but cost of 1 is going to be incurred.(K+C+1).
Average Cost incurred for performing K+1 operations: (K+C+1)/(K+1) .
=(1+C/K), Since C<=K then we have the above condition with Cost/Operation: <=2
Average cost per operation=(1+C/K) <=2 Dollars.