[10] A PowerStack consists of a potentially infinite series of stacks So, S1, S2,..., where the i-th stack S, can hold up to 21 elements. In this question, we study the following PowerPush operation for an PowerStack. The main working mechanism of a PowerPush is the following: whenever there is an attempt to Push an element onto any full stack Si, we first Pop all the elements off Si and Push them onto stack Si+1 to make room. If Si+1 is already full, we first recursively move all its members to Si+2, etc. Each PowerPush operation starts by attempting to Push to So. Assume that each elementary Push and Pop operation takes 1 unit of time, and the cost of any other operation (e.g., checking if a stack is full) is ignored (a) In the worst case, how many units of time does it take to PowerPush one new element onto a PowerStack containing n elements? Your answer should be in exact form (i.e., not in asymptotic notation) and justified. (b) Consider performing a sequence of n PowerPush operations onto a PowerStack that is initially empty. Show that the amortized runtime per operation is O(log n) Hint: You can first try to analyze it using the aggregate method, which is doable but quite complicated; then you should try the accounting method and realize that it becomes much simpler [10] A PowerStack consists of a potentially infinite series of stacks So, S1, S2,..., where the i-th stack S, can hold up to 21 elements. In this question, we study the following PowerPush operation for an PowerStack. The main working mechanism of a PowerPush is the following: whenever there is an attempt to Push an element onto any full stack Si, we first Pop all the elements off Si and Push them onto stack Si+1 to make room. If Si+1 is already full, we first recursively move all its members to Si+2, etc. Each PowerPush operation starts by attempting to Push to So. Assume that each elementary Push and Pop operation takes 1 unit of time, and the cost of any other operation (e.g., checking if a stack is full) is ignored (a) In the worst case, how many units of time does it take to PowerPush one new element onto a PowerStack containing n elements? Your answer should be in exact form (i.e., not in asymptotic notation) and justified. (b) Consider performing a sequence of n PowerPush operations onto a PowerStack that is initially empty. Show that the amortized runtime per operation is O(log n) Hint: You can first try to analyze it using the aggregate method, which is doable but quite complicated; then you should try the accounting method and realize that it becomes much simpler