Question

The time complexity of converting a prefix notation to infix notation is _________

(a) O(n) where n is the length of the equation

(b) O(n) where n is number of operands

(c) O(1)

(d) O(logn) where n is length of the equation

Question is taken from Application of Stacks in section Application of Stacks of Data Structures & Algorithms I

The question was posed to me in a national level competition.

Answer 1

The correct answer is (a) O(n) where n is the length of the equation

Explanation: The processes that are involved are reversing the equation (O(n)), pushing them all onto the stack(O(n)), and popping them one by one and solving them (O(n)). Hence the answer is O(n) where n is the length of the equation.