Question

An Antique dealer needs to store records of the items in the inventory into a stack (the dealer believes that keeping items longer will be beneficial; nonetheless, the business logic here is not important!). Besides the usual push() and pop(); the dealer needs to always know what is the most expensive item in the inventory/stack. You are hired to implement a new method, called max(), which returns the current maximum value for any item in the stack. Notice that the stack grows and shrinks dynamically as elements are added or removed from the stack (i.e. the contents of the stack are not fixed).

a. Write the pseudocode of the max() method.

b. What is the Big-O complexity of your solution? Explain clearly how you obtained such complexity.

c. Is it possible to have all three methods (push(), pop() and max()) be designed to have a complexity of O(1)? If no; explain why this is impossible. If yes; provide the pseudocode of the algorithm that would allow O(1) for all three methods

Answer 1