Suppose that we have a data structure called reversing stack. This data structure supports only one operation called REVERSING-PUSH. In each REVERSING-PUSH, an object is rst pushed onto the stack, and then we check if the number of items in the stack is a power of 2. If it is not, we terminate the REVERSING-PUSH. If it is, then we reverse the content of the stack, that is, we swap the object on the top of the stack with the object on the bottom, the second topmost object with the second bottommost object, and so on. For example, if we use REVERSING-PUSH to push objects 1, 2, 3, 4, 5, 6, 7, 8, 9 onto the stack, the stack contents, when listed from bottom to top, after each operation are

(1), (2, 1), (2, 1, 3), (4, 3, 1, 2), (4, 3, 1, 2, 5), (4, 3, 1, 2, 5, 6), (4, 3, 1, 2, 5, 6, 7), (8, 7, 6, 5, 2, 1, 3, 4), (8, 7, 6, 5, 2, 1, 3, 4, 9)

Use all the three methods for amortized analysis taught in class (aggregate, ac- counting and potential) to show that REVERSE-PUSH runs in O(1) amortized time. In your analysis, you can assume that the cost of reversing the content of the stack is equal to the number of objects currently in the stack (think about why this is a valid assumption). Hint: It may be helpful to think of the largest power of 2 that is less than or equal to n.