the minimization of *linear functions*.

Let $n\in\mathbb{N}$ be a positive integer. A function $f\colon\{0,1\}^n\to\mathbb{R}$ on $n$ bits is *linear*, if there exists weights $w_1,\dots w_n \in \mathbb{R}$ such that $$f(x)=\sum_{i=1}^n w_i x_i$$ for all $x\in\{0,1\}^n$. In [@DrosteJW02] it has been argued and it is easily seen that in the analysis of upper bounds of the expected optimization time of the (1+1) EA on linear functions we may assume without loss of generality that the weights $w_i$ are all positive and sorted, that is, $$\label{eq:monotone}
0<w_1\le w_2\le\dots\le w_n.$$ We simply call such weights *monotone*. Moreover, for the runtime bounds we consider in this work it does not matter whether the (1+1) EA minimizes or maximizes the linear function. This is true since maximizing a function $f$ is equivalent to minimizing $-f$ and vice versa (for $-f$ we again have to invoke above argument which allows us to assume monotonicity of the weights).

Thus, from now on, we suppose that every linear function satisfies condition (\[eq:monotone\]). Furthermore, we formulate all results for the minimization problem, even if the referenced results originally considered the problem of maximizing linear functions.

We have already seen two prominent examples of linear functions, namely the functions [<span 