Question 5: (a) Suppose we modify the standard StackType ADT studied in class by

Question

Question 5: (a) Suppose we modify the standard StackType ADT studied in class by adding a Min() member function, that returns the smallest item currently in the stack. (Assume that operators is available for ItemType.) What is the O0 time complexity of Min0)? Justify your answer. (1 mark) (b) Suppose we add to StackType a min member variable, to store the smallest value. Now Min() will be O(I), but what are the changes required to Push) and Pop), and their O0 time complexity? Explain. (2 marks) (c) Generalizing your observations above, explain how we could modify Min), Push() and Pop(0, so that all three operations have O(1) time complexity. Explain clearly your design (no code is required). (3 marks)

Explanation / Answer

a) min() will have complexity of O(n) where n is the number of element currently present in the stack. The code initially consider the top element to be minimum. Then it will loop to the bottom of the stack comparing all elements in the stack with the minimum and update minimum as and when required.

b) If we have a global variable min to store the minimum so that every call to min() will not require to look into the stack every time.
By adopting such design:
   push will take O(1) amount of time since push(x) will only compare x with min and update min if required

   pop will take O(n) amount of time, because if the top item of the stack is the equal to min, it will require loop to the bottom of the stack comparing all elements in the stack with the minimum and update minimum as and when required.

c) To achive time complexity of O(1) for all push(), pop() and min() we need another stack that will store the minimum values.
Explanation:

We have two stacks:
   1. Data stack to store data
   2. Min stack to store the minimum

When we perform push operation, we also need to push the updated minimum value into the minimum stack. To calculate the new minimum while push operation we need to check the stack top with the current input and push the minimum of those into the minimum stack

When we perform pop, we pop element from both the stacks

When we call min(), it simply returns the stack-top of the min-stack

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.