What is the time complexity of finding the FIRST and FOLLOW sets?
$\mathbf{first}_1$ and $\mathbf{follow}_1$ as relations over the symbols of a grammar $\mathcal{G}$ can be computed for a given non-terminal in $\Theta(|\mathcal{G}|)$, wnere the size of $\mathcal{G}$ is defined in a an intuitive way (basically, the sum of the lengths of the productions). 

It's clear that $|\mathcal{G}|$ is a lower limit since no algorithm could work without considering every symbol of every production of the grammar. An algorithm which takes time linear to the size of the grammar (with a proof of time complexity) is provided in section 5.5 of Parsing Theory, Vol. 1 (S. Sippu &amp; E. Soisalon-Soininen, 1988). (If $k\gt 1$, a polynomial term is introduced because of the size of the $FIRST_k$ sets.)

Thus, to compute the entire relation requires $O(|\mathcal{G}|\cdot|T|)$, where $T$ is the set of terminal symbols in $\mathcal{G}$. The $|T|$ factor (which could, in the worst case, be $O(|\mathcal{G}|)$) is the result of having to perform set union operations on sets of up to $|T|$ elements. In practice, there is no advantage to attempting to compute the $FIRST$ and $FOLLOW$ sets for an individual non-terminal; there is a lot of overlap in the individual computations.

These results were not new; the bibliography credits Donald B. Johnson &amp; Ravi Sethi (1976) A characterisation of LL(1) grammars, but a paywall impedes my verification. The algorithms are also cited in Hunt, Szymanski &amp; Ullman (1977) Operations on Sparse Relations, which refers to a 1974 paper by the same authors, with roughly the same name (paywalled, but you might be able to find it). 

By way of a side note, the framework of relational expressions developed and used by Sippu &amp; Soisalon-Soininen throughout the two volumes of Parsing Theory is a thing of beauty which for me was sufficient to justify my investment in the textbook. But you might be able to find it in a good academic library.