Amortized analysis of stacks. Consider a stack with three operations: Push, Pop,
ID: 3816020 • Letter: A
Question
Amortized analysis of stacks. Consider a stack with three operations: Push, Pop, and MultiPop(k). The MultiPop(k) operation is implemented as a series of k pops. Push and Pop each take 1 unit of time, and MultiPop(k) takes k units of time. Using amortized analysis, we determined that the average cost of an operation, over n operations, was 2 units of time.
Suppose that in addition to MultiPop(k), we want to implement a new operation MultiPush(k), which is a series of k pushes. Can we modify our amortized analysis to this case? Does amortized analysis help in this case? Why or why not? (Hint: think about what it means for amortized analysis to ‘help’. When would we want to use amortized analysis over standard analysis?)
Explanation / Answer
Scenario:
A stack with 3 operations, Push, Pop and MultiPop(k). The average cost of an operation over "n" number of operations were 2 units of time using Amortized Analysis.
Required : To add one more operation of MultiPop(k) along with other 3 operations where k is a series of pushes on to the stack. We are to analyze if amortized analysis can be used over here.
About Amortized Analysis : Amortized analysis is process of analyzing the time complexity of a given algorithm such that how much time and memory constraints are utilized by a resourse in the execution of operations present in a program.
Explaination :
Yes, we can use the help of amortized analysis in case of addition of MultPush(k) operation on the stack. Reason : The time complexity of Multipush operations depends on the number of pushes. Assuming one multpush operation takes O(m) time, so n multipush operations for m elements to be pushed on to the stack will take O(nm) time which leads to an amortized cost of O(m). Hence, Amortized analysis would be suitable here also because the operation to be performed is fixed i.e Multipush(k) and not random.
Amortized analysis over Standard Analysis :
Usually Amortized analyis is preferred over Standard analysis as execution operations are so fast that it can be well governed by amortized running time. The running time of such operations are not small so using amortized analysis would always be suitable here.
Eg: A very apt example of this is Memory management in C# using Garbage collection. The garbage collection is slow depending on when the garbage collector is invoked but the amortized cost is efficient and can be managed.
Standard Analysis is suitable in cases when the data used within the execution of program is random. for instance, doing an analysis of modelling a large program may include a random number, that can be well analyzed with standard analysis. In such cases, other parts may not required randomness as well to achieve stablity in operation. So, standard analysis could be effective here.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.