Let I(|G|, |w|) denote the maximum number of items in the top cell of the table. Then, based on the CKY table, I(|G|, |w|) can be stated as a recurrence:
I(|G|, 1) = |G|I(|G|, |w|) = |G| * [I(|G|, |w| - 1) * I(|G|, 1) + I(|G|, |w| - 2) * I(|G|, 2) + ... + I(|G|, 1) * I(|G|, |w| - 1]The max number of items in the entire table is then 1*I(|G|, |w|) + 2*I(|G|, |w-1|) + ... + |w|*I(|G|, 1).
Since the term I(|G|, |w| - 1) * I(|G|, 1) appears in the expression twice, I(|G|, |w|) must be at least twice I(|G|, |w-1|) for all |w| > 2. Therefore, the number of items in the top cell and in the table grows exponentially, although we don't know the exact complexity because we haven't tried to approach that nasty recurrence yet.
From the above, the complexity must be exponential.
[X, L, i, j] where L refers to a list of items rather than individual items?The maximum number of items in this case is O(|G| * |w|2), since each cell of the table may have at most |G| items. The maximum size of the list for each item is O(|G| * |w|), because there are O(|w|) pairs of cells that the elements of the list could point to, and O(|G|) possible pairs of symbols for each pair of cells, since there are only |G| rules.
Therefore, the spatial complexity is O(|G|2 * |w|3).