Chomsky normal form complexity

Question

How to prove that the complexity of transforming any context-free grammar without epsilon productions to chomsky normal form is $ O(N^2) $ , because I found this in 2 articles, but without proof

Answer 1

As far as I know, this is textbook stuff so the proofs are obviously not found in articles. However if I remember correctly, you get to Chomsky normal form by first replacing any terminals in something like $$A \rightarrow BCst$$

by some extra nonterminal symbols

$$A \rightarrow BCST$$ $$S \rightarrow s$$ $$T \rightarrow t$$

and then in the second step you replace longer rules like

$$A\rightarrow BCD$$

with again additional nonterminals

$$A\rightarrow BA'$$ $$A'\rightarrow CD$$

I think it is easy to see that each replacement step only needs $O(n)$ of work per rule, so you end up with $O(n^2)$, since the number of rules is clearly bounded by $n$.