What is the time complexity of an infix to postfix conversion algorithm?
2023
What is the time complexity of an infix to postfix conversion algorithm?
- A.
O(N log N)
- B.
O(N)
- C.
O(N2)
- D.
More than one of the above
- E.
None of the above
Attempted by 708 students.
Show answer & explanation
Correct answer: B
The time complexity of converting an infix expression to postfix using a stack-based algorithm is O(N), where N is the number of characters in the expression. Step 1: Each character in the infix expression is processed exactly once. Step 2: For each operator, stack operations (push/pop) are performed in O(1) time. Step 3: Since every element is processed once and stack operations are constant time, the total time complexity is O(N).