Sharp Bounds on the Runtime of the (1+1) EA via Drift Analysis and Analytic Combinatorial Tools

Hsien-Kuei Hwang, Carsten Witt

The expected running time of the classical (1+1) EA on the OneMax benchmark function has recently been determined by Hwang et al. (2018) up to additive errors of $O((\log n)/n)$. T…