1,098 views
Which of the following is TRUE regarding the running time of a LR(1) parser?
1. It runs in linear time for all inputs
2. It runs in polynomial time but not necessarily $O(n^3)$ for all inputs
3. For some inputs it may take exponential time
4. It runs in $O(n^3)$ but not always $O(n^2)$

So how can option A be true ?
From the above image isn't A option straight forward?

For LR parsers the ideal time complexity is linear time but some methods may take O(n^3)  time in the worst case.

so,In more general way, good to take it as an ideal condition, the answer will be A.