Quickly finding empty-string producing nonterminals in a CFG
Can't one implement that algorithm in linear time as follows? (Warning I haven't proof-read this too carefully, so bugs are likely.)

In what follows whenever I say "production" I mean to include only those that include no terminals.
Build a list, for each non-terminal, of the productions it appears in. For every production $i$ let $c_i$ count how many distinct non-terminals in the right hand side are currently marked non-nullable. Let $Q$ denote a queue of non-terminals that have been marked nullable but not yet processed. Initialize all $c_i$ to the number of distinct non-terminals in the right hand side of production $i$. Initialize all non-terminals to not nullable. For every non-terminal $Z$ generated by production $i$ with $c_i=0$ add $Z$ to $Q$ and mark $Z$ as nullable.

While $Q$ is non-empty, remove an arbitrary non-terminal $X$ from $Q$ and process it as follows. For every production $j$ that $X$ is in, decrement $c_j$. If a $c_j$ becomes zero, check to see if the corresponding non-terminal $Y$ has been marked nullable already. If not, mark $Y$ nullable and add $Y$ to $Q$.