What is the space complexity of the CYK algorithm for the P table, where n is…
2026
What is the space complexity of the CYK algorithm for the P table, where n is the number of words in the sentence and m is the number of non terminal symbols in the grammar?
O(n3)
O(nm2)
O(n2m)
O(n2m2)
- A.
1
- B.
2
- C.
3
- D.
4
Attempted by 44 students.
Show answer & explanation
Correct answer: C
The space complexity of the CYK (Cocke–Younger–Kasami) algorithm is (O(n2 .m)), where (n) is the length of the input string and (m) is the number of non-terminal symbols in the grammar. This is because the algorithm uses a two-dimensional table to store results for all possible substrings of the input, and there are (O(n2)) such substrings. For each table entry, a set of non-terminals (up to (m)) is stored to indicate which symbols can generate that substring. Therefore, the total space required is proportional to (n2 times m), giving a space complexity of (O(n2 .m)).