Exercise 17.1-1

If the set of stack operations included a MULTIPUSH operation, which pushes \(k\) items onto the stack, would the \(O(1)\) bound on the amortized cost of stack operations continue to hold?

No. The addition of MULTIPUSH into our set of stack operations (alongside PUSH, POP and MULTIPOP) results in the new possibility that we may add multiple values to the stack in a single operation. The cost of MULTIPUSH(\(S\), \(k\)) is \(\Theta(k)\) and so our new average runtime will be \(\Theta(k)\) rather than \(O(1)\).