Which of the following is correct?

Which of the following is correct?
a) Top-down parser complexity is O(n4)
b) Bottom-up parser complexity is O(n3)

(A) True, False
(B) False, True
(C) True, True
(D) False, False

Answer

(C) True, True

1Comment
Abhishek Tiwari @abhishekssj5 20 Dec 2015 12:44 pm

O(n^4) time complexity is for parsing left recursive grammar in CYK algorithm while here Top-down parser is given which is supposed to be free from Left recursion and left factoring.

https://en.wikipedia.org/wiki/Top-down_parsing

 

 

Pages