The CYK algorithm parses a CFG in CNF. Its time complexity for a string of length $n$ is

1. CYK (Cocke-Younger-Kasami) parses by DYNAMIC PROGRAMMING. 2. Build a 2D table $T[i][j]$ where $T[i][j]$ = set of non-terminals that can derive the substring from position $i$ to $j$. 3. Fill the table bottom-up: - For length-1 substrings: $T[i][i] = \{A : A \to s_i \in R\}$. - For longer substrings $[i,j]$: try every split $k$ in $i \leq k < j$ and every rule $A \to BC$ with $B \in T[i][k]$ and $C \in T[k+1][j]$. 4. Complexity: - $O(n^2)$ substrings (cells in the table) - For each cell, $O(n)$ split points - For each split, $O(|R|)$ rules 5. Total: $O(n^3 \cdot |R|)$. With $|R|$ treated as constant: $O(n^3)$. 6. Faster algorithms exist for specific grammar classes (LL parsing is linear for LL(k) grammars). $O(n^3)$ is the general CFG parsing complexity. _Source: Jeff Erickson, "Models of Computation", §5.9 (CYK Parsing Algorithm)._