UGC NET CSE | December 2025 | Part 2 | Question: 71

Question

What is the space complexity of the CYK algorithm for the $\mathrm{P}$ table, where $\mathrm{n}$ is the number of words in the sentence and $\mathrm{m}$ is the number of non terminal symbols in the grammar?

• A. $\mathrm{O}\left(\mathrm{n}^{3}\right)$
• B. $\mathrm{O}\left(\mathrm{nm}^{2}\right)$
• C. $\mathrm{O}\left(n^{2} m\right)$
• D. $\mathrm{O}\left(\mathrm{n}^{2} \mathrm{~m}^{2}\right)$

Answer 1

Option C

Space Complexity: O(n^2m)

Time complexity : O(n^3m^3)