  We study the greedy independent set algorithm on sparse Erd\H{o}s-R\'enyi
random graphs ${\mathcal G}(n,c/n)$. This range of $p$ is of interest due to
the threshold at $c=e$, beyond which it appears that greedy algorithms are
affected by a sudden change in the independent set landscape. A large deviation
principle was recently established by Bermolen et al. (2020), however, the
proof and rate function are somewhat involved. Upper bounds for the rate
function were obtained earlier by Pittel (1982). By discrete calculus, we
identify the optimal trajectory realizing a given large deviation and obtain
the rate function in a simple closed form. In particular, we show that Pittel's
bounds are sharp. The proof is brief and elementary. We think the methods
presented here will be useful in analyzing the tail behavior of other random
growth and exploration processes.
