This is because each prediction step now has O(n) choices, since they need to expand nodes like VP[1, 6] as: where the midpoint i in general has O(n) choices (just like in CKY).
their grammar constant c becomes O(n).