Solving the Hamilton cycle problem fast on average

We present CertifyHAM, a deterministic algorithm that takes a graph G as input and either finds a Hamilton cycle of G or outputs that such a cycle does not exist. If $G\sim G(n,p)$ and $p\displaystyle \geq\frac{100\log n}{n}$ then the expected running time of CertifyHAM is $O\left(\displaystyle \frac{n}{p}\right)$ which is best possible. This improves upon previous results due to Gurevich and Shelah, Thomason and Alon, and Krivelevich, who proved analogous results for p being constant, $p\geq 12n^{-1/3}$ and $p\geq 70n^{-1/2}$ respectively.