What is the space complexity of the CYK algorithm for the P table, where n is…
2025
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?
Answer: C. O(n2m) — Concept: the space a dynamic-programming parser needs is (number of table cells) times (space one cell occupies). For a chart-parsing table the cells are…
- A.
O(n3)
- B.
O(nm2)
- C.
O(n2m)
- D.
O(n2m2)
Attempted by 158 students.
Show answer & explanation
Correct answer: C
Concept: the space a dynamic-programming parser needs is (number of table cells) times (space one cell occupies). For a chart-parsing table the cells are indexed by the contiguous substrings, called spans, of the input, and each cell stores the set of grammar symbols that can derive that span - so the two factors are how many spans exist and how large a symbol set can be.
Application - CYK on a sentence of n words with a Chomsky-Normal-Form grammar of m non-terminals:
The table P has one cell per span. A sentence of n words has n(n+1)/2 spans, which is O(n2) cells.
Cell P[i, j] holds the set of non-terminals that derive the span starting at word i with length j. A set drawn from m non-terminals occupies O(m) space - m bits as a bit-vector, or at most m symbols as a list.
Multiplying the two factors gives O(n2) times O(m) = O(n2m) for the whole P table.
Cross-check - what each of the four expressions actually counts:
Expression | What it counts |
|---|---|
O(n3) | (start, split, end) index triples - the loop count behind CYK’s running time, not anything that is stored |
O(nm2) | ordered non-terminal pairs (B, C) at each of n word positions - one span length, not all spans |
O(n2m) | every span paired with every non-terminal - exactly the contents of the P table |
O(n2m2) | every span paired with every ordered non-terminal pair - pairs are examined transiently while a cell is filled, they are not stored in it |
Hence the P table occupies O(n2m) space. The often-quoted O(n3·|G|) figure is CYK’s time complexity, driven by the extra split-point loop, and must not be confused with its storage.
Explore the full course: Mppsc Assistant Professor Computer Science Paper 2