drift theorem, we make use of the simple linear function $g\colon \{0,1\}^n \to \mathbb{R}$, chosen as $$g(x)=\sum_{i=1}^n \Big(1+\frac{i}{n}\Big)x_i.$$ This function $g$ serves us as a potential function for all linear functions $f\colon \{0,1\}^n \to \mathbb{R}$ with $$f(x)=\sum_{i=1}^n w_i x_i$$ and monotone weights $0<w_1\le\dots \le w_n$. Using parts of Jägersküpper’s analysis [@Jagerskupper08], we then improve his upper bound on the expected optimization time of the (1+1) EA on linear functions to $(1+o(1)) 1.39 {\mathrm{e}\xspace}n \ln(n)$.

We also give lower bounds for this problem. We show that, in the class of all functions with a unique global optimum, the function [<span style="font-variant:small-caps;">OneMax</span>]{}(see (\[eq:onemax\])) has the smallest expected optimization time. This extends the lower bound of $(1 - o(1)) {\mathrm{e}\xspace}n \ln(n)$ for the expected optimization time of the (1+1) EA on [<span style="font-variant:small-caps;">OneMax</span>]{} [@DoerrFW10] to all functions in that class (including all linear functions with non-zero coefficients).

Together with our upper bound, we thus obtain the remarkable result that all linear functions have roughly (within a 39% range) the same optimization time.

To further demonstrate the strength of multiplicative drift analysis, we give straight-forward analyses for three prominent combinatorial problems. We consider the problems of computing minimum spanning trees (MST), single-source shortest paths 