The (1+1) Elitist Black-Box Complexity of LeadingOnes∗
Carola Doerr1,2, Johannes Lengler3

arXiv:1604.02355v1 [] 8 Apr 2016

1 CNRS,

2 Sorbonne

UMR 7606, LIP6, 75005 Paris, France
Universités, UPMC Univ Paris 06, UMR 7606, LIP6, 75005 Paris, France

3 Institute

for Theoretical Computer Science, ETH Zürich, Switzerland

January 12, 2018

Abstract
One important goal of black-box complexity theory is the development of complexity models allowing to derive meaningful lower bounds for whole classes of randomized
search heuristics. Complementing classical runtime analysis, black-box models help us
understand how algorithmic choices such as the population size, the variation operators,
or the selection rules influence the optimization time. One example for such a result is
the Ω(n log n) lower bound for unary unbiased algorithms on functions with a unique
global optimum [Lehre/Witt, GECCO 2010], which tells us that higher arity operators or biased sampling strategies are needed when trying to beat this bound. In lack
of analyzing techniques, almost no non-trivial bounds are known for other restricted
models. Proving such bounds therefore remains to be one of the main challenges in
black-box complexity theory.
With this paper we contribute to our technical toolbox for lower bound computations by proposing a new type of information-theoretic argument. We regard the
permutation- and bit-invariant version of LeadingOnes and prove that its (1+1) elitist black-box complexity is Ω(n2 ), a bound that is matched by (1+1)-type evolutionary
algorithms. The (1+1) elitist complexity of LeadingOnes is thus considerably larger
than its unrestricted one, which is known to be of order n log log n [Afshani et al.,
2013].

1

Introduction

Since the seminal paper of Droste, Jansen, and Wegener [DJW06] black-box complexity is
the most accepted complexity measure for black-box search heuristics such as evolutionary
∗

An extended abstract of this paper will appear at GECCO 2016.

1

Model
unrestricted
unbiased, arity 1
unbiased, arity 2
unbiased, arity ≥ 3
ranking-based unbiased, arity ≥ 3
elitist, arity 1

Lower Bound
Ω(n log log n) [AAD+ 13]
Ω(n2 )
[LW12]
Ω(n log log n)
Ω(n log log n)
Ω(n log log n)
Ω(n2 )
this paper

Upper
O(n log log n)
O(n2 )
O(n log n)
O(n log(n)/ log log n)
O(n log(n)/ log log n)
O(n2 )

Bound
[AAD+ 13]
[Rud97] for (1+1) EA
[DJK+ 11]
[DW12]
[DW12]
[DJW02]

Table 1: Known black-box complexities of LeadingOnes. The lower bounds for higher
arities follow from the lower bound in the unrestricted model.
algorithms (EAs). Informally, the black-box complexity of a set F of functions is the minimum expected number of function evaluations that are needed to solve any problem instance
f ∈ F , where the minimum is taken over a class of algorithms A. The original black-box
model by Droste, Jansen, and Wegener regards as A the whole collection of possible blackbox algorithms. It is therefore called the unrestricted black-box model. However, unlike in
classical complexity theory where a widely accepted complexity notion is used, several blackbox complexity models co-exist in the theory of randomized search heuristics. Each model
regards a different collection A of algorithms (e.g., the memory-restricted model regards
only such algorithms that keep in the memory only a limited number of previously sampled
search points while in contrast the algorithms in the unrestricted black-box are assumed to
have full access to all previous function evaluations). When we compare the black-box complexity of a problem in the different models, we thus learn how certain algorithmic choices
such as the population size, the variation operators in use, or the selection rules influence
the performance of the search heuristics.
At GECCO 2015 [DL15a] we have presented a new black-box model that combines several
of the previously regarded restrictions such as the size of the memory and the selection rules.
More precisely, we have defined a collection of (µ+λ) elitist black-box models, where a (µ+λ)
elitist algorithm is one that keeps at any point in time the µ best-so-far sampled solutions.
In the next iteration it is allowed to use only the relative (not absolute) function values of
these µ points to create some λ new search points. Truncation selection is then used to
select from these µ + λ points the µ surviving ones that form the parent population of the
next iteration. A (µ + λ) black-box algorithm is thus in particular a memory-restricted and
ranking-based one in the sense of [DJW06, DW14a] and [DW14b], respectively. In addition,
it has to employ truncation selection as replacement rule.
In [DL15a] examples are presented for which the elitist black-box complexity is much
larger than in any of the previously existing black-box models, while in [DL15b] it is shown
that the complexity of OneMax is of linear order only even for the most restrictive (1+1)
setting. Here in this work we regard another classic problem, a generalized version of the
LeadingOnes function. We show that its (1+1) elitist black-box complexity matches the
performance of typical evolutionary algorithms.

2

1.1

The LeadingOnes Problem

LeadingOnes (Lo for short) is among the best-studied functions in the theory of evolutionary
computation. It was originally designed in [Rud97] to disprove the conjecture of Mühlenbein [Müh92] that the expected runtime of the (1 + 1) EA on every unimodal function is
O(n log n). While Rudolph showed experimentally that its expected runtime is Θ(n2 ), this
bound was proved a bit later in [DJW02]. Quite exact bounds for the expected runtime of
the (1 + 1) EA on Lo have been shown in [BDN10, Sud13, Lad05].
As argued in [DW12], most EAs behave symmetrically with respect to function representation, and it is therefore natural that the proven performance guarantees extend to the class
of generalized Lo functions which contains all pseudo-Boolean functions f : {0, 1}n → R
having a fitness landscape that is isomorphic to that of the original Lo function (which
assigns to each bit string the number of initial ones, cf. Section 2 for precise definitions).
The (1 + 1) EA qualifies as a (1+1) elitist algorithm in the sense of [DL15a]. The abovementioned runtime bounds therefore imply that the (1+1) elitist black-box complexity of
Lo is of order at most n2 . We show that this is bound is tight.

1.2

Discussion of Our Result

Our main result is summarized by the following statement.
Theorem 1. The (1+1) elitist black-box complexity of Lo is Θ(n2 ).
As mentioned, this bound is matched by the average performance of the (1 + 1) EA. It is
also matched by the expected runtime of Randomized Local Search (RLS), thus showing that
these two simple strategies are asymptotically optimal for Lo among all (1+1)-type elitist
algorithms. Our result also shows that an algorithm trying to beat the Ω(n2 ) bound (and
such algorithms exist, cf. below) has to use larger population sizes or non-elitist selection
strategies.
In our proof we will not make use of the fact that elitist algorithms have to be rankingbased; that is, the (1+1) elitist black-box complexity of Lo remains Θ(n2 ) even if the
algorithms have access to the absolute fitness value of the current search point.
We summarize all known black-box complexities of Lo in Table 1. Relevant for our contribution are in particular the tight Θ(n log log n) bound for the unrestricted black-box complexity of Lo obtained by Afshani, Agrawal, Doerr, Doerr, Larsen, and Mehlhorn [AAD+ 13],
the O(n log n) bound for the binary unbiased black-box complexity by Doerr, Johannsen,
Kötzing, Lehre, Wagner, and Winzen, [DJK+ 11], and the Ω(n2 ) bound for the unary unbiased model by Lehre and Witt [LW12]. Note also that already simple binary search exhibits
a complexity of only O(n log n) on the Lo problem (cf. [AAD+ 13] for an implementation of
the binary search strategy). This is why it is remarkable that (1+1) elitist algorithms have
such a rather weak performance on Lo.
Our result is not the first lower bound of quadratic order for the Lo problem. In fact,
Lehre and Witt proved in [LW12] that all unary unbiased search strategies, i.e., intuitively
speaking, all black-box algorithms using only mutation as variation operators, need Ω(n2 )
3

function evaluations on average to optimize this problem. Combining our result with theirs,
we see that even if we replace the mutation operator in RLS (which flips exactly one bit,
chosen uniformly at random) or the (1+1) EA (which flips independently each bit with
probability 1/n) by a—possibly strongly—biased one, the resulting algorithm would still need
time Ω(n2 ) on average. This shows that not only unbiased sampling, but also the population
structure of the algorithm and the selection strategies determine the comparatively slow
convergence of these two well-known search heuristics.
In addition to identifying such structural bottlenecks, our result is also—and this is in
fact the main motivation for our studies—interesting from a purely mathematical point of
view, as we need to develop some new tools for the lower bound proof. Specifically, we
use some information-theoretic arguments, utilizing that the amount of information that
the algorithm has at any given point is not sufficient to make substantial progress. Such
information-theoretic arguments are notoriously hard to formulate rigorously, and are even
harder to employ in a non-trivial situation like ours.
What complicates our analysis is the fact that the Lo functions, in principle, allow for a
rather huge storage. Indeed, when the fitness of an individual is k for some k < n, then all
but the k + 1 bits determining the fitness of the search point can be used for storing information about previous samples, the number of iterations elapsed, or any other information
gathered during the optimization process. We recall that such strategies of constantly storing information about previous samples are at the heart of many upper bounds in black-box
complexity, cf., for example, the proofs of the O(n/ log n) bound for the (1+1) memoryrestricted [DW14a], the ranking-based [DW14b] or the (1+1) elitist Monte Carlo [DL15b]
black-box complexity of OneMax. We therefore need to show that despite the fact that
changing the n − (k + 1) irrelevant bits has no influence on the fitness, the algorithm cannot
make effective use of this storage space.
The intuitive reason why the given storage is not large enough is that by the permutationinvariance of the Lo problem the black-box algorithms do not know where the irrelevant bits
are located, and storing this information would require more bits than available. However,
the discrepancy is rather small: in most parts of the process, if the number of bits of the
storage space was larger by just a constant factor, then this would trivially allow for efficient
use of the storage, and the lower bounds would break down. It is thus essential to find
a good measure for the information that an algorithm can possibly encode in its queries.
We develop a precise notion that bounds the amount of information that the algorithm has
about the function Loz,σ at any given state. We can use this notion to estimate the gain
that the algorithm can draw from any given amount of information. We consider one of the
main contributions of our paper to make these intuitive concepts precise and utilizable in
proofs. Although our definitions are adapted to the Lo problem, we are optimistic that the
developed techniques are applicable also to other black-box settings and, of course, also to
other problem classes.
A second difficulty that we face in our proof is that the the minimax principle of
Yao [Yao77]—which is the foremost technique in black-box complexity theory to prove lower
bounds—cannot be applied to the elitist model, as discussed in [DL15a]. We therefore need

4

Algorithm 1: The (µ + λ) elitist black-box algorithm for maximizing an unknown
function f : {0, 1}n → R
1 Initialization:
2
X ← ∅;
3
for i = 1, . . . , µ do
4
Depending only on the multiset X and the ranking ρ(X, f ) of X induced by f ,
choose a probability distribution p(i) over {0, 1}n and sample x(i) according to
p(i) ;
5
X ← X ∪ {x(i) };
6
7

8
9

Optimization: for t = 1, 2, 3, . . . do
Depending only on the multiset X and the ranking ρ(X, f ) of X induced by f
choose a probability distribution p(t) on ({0, 1}n )λi=1 and sample (y (1) , . . . , y (λ) )
according to p(t) ;
Set X ← X ∪ {y (1) , . . . , y (λ) };
for i = 1, . . . , λ do Select x ∈ arg min X and update X ← X \ {x}

to find an extension of the elitist model that is generous enough to allow for the application
of the information-theoretic tool but that does, at the same time, not decrease the black-box
complexity by too much.

2
2.1

Formal Definitions
Black-box Complexity

We come to the formal definitions. A (µ + λ) elitist black-box algorithm is a (possibly
randomized) algorithm that can be described by the framework of Algorithm 1. I.e., assume
that a pseudo-Boolean function f : {0, 1}n → R is given, the fitness function. Then the
algorithm maintains a multiset X of µ search points, which is called the population. It is
initialized by sampling iteratively µ search points, which may only depend on the previous
search points and the ranking induced on them by the fitness function f . Afterwards, in
each round it samples λ new search points (offspring) based only on the search points in X
and their ranking with respect to f . It then forms the new population by choosing the µ
search points from the old population and the offspring that have the largest fitness, where
it may break ties arbitrarily. This process is repeated until a maximum of f is sampled.
The runtime of a (µ + λ) elitist black-box algorithm A on a pseudo-Booloean f is the
number of search points (queries) that A samples before it samples for the first time a
maximum of f . The expected runtime of A on a class F of pseudo-Boolean functions is
the maximum expected runtime of A on f , where f runs through F . The (µ + λ) elitist
black-box complexity of F is the smallest expected runtime of a (µ + λ) elitist black-box
algorithm on F .
5

Remark 2. In [DL15a] we distinguished between two different notions of runtime, which
in turn lead to different notions of (elitist) black-box complexity: the Las Vegas runtime of
a black-box algorithm A on a function f is the expected number of steps until A finds the
optimum of f , while the p-Monte Carlo runtime is the minimal number of steps A needs in
order to find the optimum of f with probability at least 1 − p. It was shown that there may
be an exponential gap between the resulting elitist black-box complexities. However, this is
not the case for Lo. Formally, we show for Lo that the (1+1) elitist Las Vegas black box
complexity is Ω(n2 ), and for every constant p > 0 the (1+1) elitist p-Monte Carlo black box
complexity is Ω(n2 ). Both statements are immediate consequences of Theorem 12.
In this paper, black-box complexity refers to the Las Vegas version unless specified otherwise.

2.2

LeadingOnes

The original Lo function is defined via Lo : {0, 1}n → R, x 7→ max{i ∈ {0, 1, . . . , n} | ∀j ≤
i : xj = 1}. This is generalized to a permutation- and bit-invariant version in the following
way. Let Sn denote the set of permutations of [n] := {1, . . . , n} and let [0..n] := {0, 1, . . . , n}.
For z ∈ {0, 1}n and σ ∈ Sn we consider the function
Loz,σ : {0, 1}n → [0..n],
x 7→ max{i ∈ [0..n] | ∀j ≤ i : zσ(j) = xσ(j) } ,
so Loz,σ (x) is the length of the longest common prefix of the search point x and the target
string z in the order σ. For i < j we say that σ(i) is more significant than σ(j). In
particular, σ(1), . . . , σ(k) are the k most significant bits, and σ(n), . . . , σ(n − k + 1) are the k
least significant bits. The Lo problem is the problem of optimizing an unknown member of
the class Lo := {Loz,σ | z ∈ {0, 1}n , σ ∈ Sn }. Clearly, the unique global optimum of Loz,σ
is z. For ease of notation we drop the subscript {z, σ} in the following.

2.3

Other Notation and Definitions

Throughout this work, we will write log x for the binary logarithm log2 x and ln x for the
natural logarithm of x. We say that an event E holds with high probability if Pr[E] → 1 for
n → ∞.
A fitness level of a function f is a maximal set of search points which have the same
fitness. In particular, every function Loz,σ has exactly n different fitness levels.

3

Proof of the Lower Bound

To prove the desired Ω(n2 ) bound we introduce a more generous model in which the algorithms have strictly more power than in the original elitist model (Sections 3.3–3.5). We then
show the Ω(n2 ) lower bound for this more generous model in Section 3.6. Before we start
6

with the technical details of the alternative model, we explain in Section 3.1 our motivation
for introducing it. We present a high-level overview of the proof in Section 3.2.

3.1

Challenges in Proving the Lower Bound

Learning from search points with inferior fitness: One may be tempted to believe
that in the (1+1) elitist model we cannot learn information from search points that have
stricty lower fitness than that of the current best one. This is indeed a tantalizing thought
as such search points have to be discarded immediately and can therefore not influence the
sampling distribution of the next query. However, one has to be very careful with such
arguments. To illustrate why it fails in general, consider the following setting: assume
that there is a search point x from which we sample search point y1 with some very small
probability ε and search point y2 otherwise; i.e., we sample y2 with probability 1 − ε. For
the sake of the argument assume further that for all search points z 6= x the probability
to sample y1 or y2 is zero. If at some stage of the algorithm we happen to have y1 in the
memory we may then conclude that we must have been at x in the previous step. Moreover,
if f (y2 ) > f (x) then with probability 1 − ε we would have proceeded to y2 , and thus we
would never have visited y1 (as we cannot return to x from a fitter search point). Therefore,
by Bayes’ theorem f (y2 ) ≤ f (x) with probability at least 1 − ε. Summarizing, although we
have not visited y2 , we can deduce information about its fitness.
Application of Yao’s Principle: A tool that has proven to be extremely helpful
in deriving lower bounds for black-box complexities is the so-called MiniMax Principle of
Yao [Yao77]. All lower bounds that we are aware of directly or indirectly use (the easy
direction of) this tool. In simple words, Yao’s Principle allows us to restrict our attention
to the performance of a best-possible deterministic algorithm on a random input. This is a
lower bound for the expected performance of a best possible randomized algorithm for this
problem. This principle is typically used with a very simple distribution p. Indeed, in most
proofs p can be chosen to be the uniform distribution.
Lemma 3 (Yao’s Principle [Yao77, MR95]). Let Π be a problem with a finite set I of input
instances (of a fixed size) permitting a finite set A of deterministic algorithms. Let p be a
probability distribution over I and q be a probability distribution over A. Then,
min E[T (Ip , A)] ≤ max E[T (I, Aq )] ,
A∈A

I∈I

(1)

where Ip denotes a random input chosen from I according to p, Aq a random algorithm
chosen from A according to q and T (I, A) denotes the runtime of algorithm A on input I.
As was pointed out in [DL15a], the informal interpretation of Yao’s principle as stated
before Lemma 3 does not apply to elitist algorithms. Since this is a crucial difficulty in our
proofs, we explain this apparent contradiction in detail, even though a very similar example
was given in [DL15a].
Let I = Lo, let p be the uniform distribution over the inputs I, and let Ip as in Lemma 3.
Then any deterministic algorithm A has a positive probability during the optimization of
7

Ip of getting stuck. Assume x and y are the first two search points that A queries, and
note that since A is an elitist black-box algorithm, the choice of y does not depend on the
fitness of x (although the example could easily be adapted to cover this case as well). If
the fitness of y is strictly smaller than that of x, y has to be discarded immediately and the
algorithm is in exactly the same state as before, and will continue sampling and discarding
y. Therefore, the expected runtime of A on this fitness function is infinite. Since this holds
for every deterministic algorithm (that is, every deterministic (1+1) elitist algorithm has
an infinite expected runtime on a uniformly chosen Lo instance), the lower bound in (1) is
infinite, too. However, of course there are randomized search strategies with finite expected
runtime, e.g., RLS and the (1 + 1) EA (see Section 1.1).
To resolve this apparent discrepancy, note that Lemma 3 makes a statement about algorithms that are a convex combination of deterministic ones. For typical classes of algorithms
this describes exactly the class of randomized algorithm, since we can emulate every randomized algorithm by making all random coin flips in advance, and then choosing the deterministic algorithm whose decisions in each step agree with these coin flips. However, this
only works if the algorithm is free to make a new decision in each step, e.g., if the algorithm
may base its decision on the number of previous steps. However, (1+1) black-box algorithms
(elitist or not) may not do so since they are memory-restricted. Therefore, randomized (1+1)
black-box algorithms cannot be in general written as convex combinations of deterministic
(1+1) black-box algorithms.
These observations have a quite severe effect on our ability to prove lower bounds in elitist
black-box models. Indeed, the only way we currently know is the approach taken below,
where we consider a superset AM of algorithms such that every randomized algorithm in
AM can be expressed as a convex combination of deterministic ones. A lower bound shown
for this broader class trivially applies to all elitist black-box algorithms. In our case, we
achieve the class AM by giving the algorithms access to enough memory to determine the
current step (within a certain phase).
If applicable, Yao’s principle allows us to restrict ourselves to deterministic algorithms,
which are usually easier to analyze. In particular, we may use the following observation.
Remark 4. Assume that we run a deterministic algorithm A on a problem instance i that
we have taken from the set of instances I uniformly at random, so Pr[i = c] = 1/|I| for every
c ∈ I. Assume further that the first queries q1 , . . . , qℓ of A reduce the number of possible
problem instances to some set C. Then Pr[i = c | q1 , . . . , qℓ ] = Pr[i = c | i ∈ C] = 1/|C| for
all c ∈ C. In particular, each c ∈ C is equally likely to be the secret instance i.

3.2

High-Level Ideas of the Proof

As explained above, we cannot use Yao’s principle directly for the set of all elitist blackbox algorithms. Instead, we use a larger class AM of algorithms, the definition of which is
adapted to the special structure of the Lo problem. In this model, whenever an algorithm
reaches fitness level k for the first time, we reveal for a brief moment the position of the
k most significant bits. Note that by symmetry of the Lo function, an algorithm cannot
8

discriminate between the less significant bits from its previous samples. Therefore, everything
that the algorithm has learned previously is covered by this piece of information. Based on
this information, we allow the algorithm to “store” whatever it wants in the m = n − k least
significant bits. After that, we occlude the information about the k significant bits again,
and the algorithm may only use its storage of size m. However, until the algorithm finds the
next fitness level we allow it to keep track of all the search points that it visits on the current
fitness level. In this way we create a class of algorithm for which Yao’s principle allows us
to restrict to deterministic algorithms. The details are spelled out in Section 3.3.
The algorithm may be lucky and skip a fitness level, because the (k + 1)-st significant bit
in its search point is correct. However, this only happens with probability 1/2. Otherwise,
the algorithm can only carry over m bits of information to the next level, cf. Lemma 8
for a precise statement. Crucially, if m = δn for some small δ > 0, then this information
is not enough to encode the positions of the k most significant bits, which would require
n
log nk = log m
≈ m(1 + log(1/δ)) bits. One strategy of the algorithm might be to store
as many of the insignificant bit positions as possible, so that it can test quickly whether one
of these candidates is the next significant bit. However, whenever the algorithm wants to
be certain (or “rather certain”) that a specific bit b is insignificant, then this decreases the
available information about the remaining bits. This strategy might pay off if b is the next
significant bit, because then the algorithm reaches a new fitness level immediately. However,
with a too high probability b is not the next significant bit, and the algorithm is left with
an even worse situation.
The key to the proof lies in the exact definition of the class AM , and in a precise way to
capture the rather vague notation of information used above. We start by defining AM in
Section 3.3. In Section 3.4 we show that by restricting to one-bit flips, we extend the runtime
of an algorithm on the k-th fitness level by at most m = n − k. In Section 3.5 we first give
a precise definition of what we mean by information, and we define the quantity Φ(k, m, B)
to be the minimum expected number of queries that an algorithm in AM using one-bit flips
needs to advance a fitness level, if there are k significant and m insignificant bits and if the
available information is B. In Lemma 10 we then give a rather straight-forward recursion for
the function Φ(k, m, B). Once the recursion is established, it is purely a matter of (somewhat
tedious) algebra to derive the lower bound Φ(k, m, B) ≥ ε(k + m)(1 − (log B)/(2m)) in
Lemma 11. Since the starting amount of information is B ≈ 2m , each algorithm using
one-bits flips needs to spend expected time Φ(k, m, 2m ) ≈ ε(k + m)/2 on the corresponding
fitness level (provided that it visits this level at all). Since using multi-bit flips can save us
at most m queries, a general algorithm in AM spends at least time ≈ ε(k + m)/2 − m on
this level, which is Ω(n) if m ≤ δn for a sufficiently small δ > 0. Thus there is a linear
number of fitness levels, such that the algorithm spends an expected linear time on each
of them, showing the Ω(n2 ) runtime. The details of this concluding argument are found in
Section 3.6.

3.3

A More Generous Model

We consider the set AM of all algorithms that can be implemented in the following model M:
9

Assume that the algorithm has queried some search points x(1) , . . . , x(t) with
maxi<t {Lo(x(i) )} = k − 1 and Lo(x(t) ) ≥ k. We say that the algorithm reaches a new
fitness level with the t-th query. In addition to letting the algorithm know that the fitness
value of x(t) is strictly larger than the previous best search point, we reveal to the algorithm
the first k significant positions σ(1), . . . , σ(k) and the corresponding bit values zσ(1) , . . . , zσ(k)
of the target string. Note that from this information the algorithm can in particular infer
that Lo(x(t) ) ≥ k, but it does not learn the precise function value of x(t) . Furthermore,
it is not difficult to see that the information revealed to the algorithm contains everything
about the unknown instance (z, σ) that the algorithm could have collect so far (and typically
it reveals much more information about the target instance than the information currently
present to the algorithm). We now allow the algorithm to “revise” its choice of the insignificant m := n − k bits of x(t) . That is, the algorithm may opt to change the entries in the
positions [n] \ {σ(1), . . . , σ(k)}, thus creating a new search point x̃(t) .
By construction, the fitness of x̃(t) is at least k. It is possibly strictly greater than k in
which case the algorithm may again revise the entries of the insignificant bits, now based on
the first k + 1 positions. This process continues until the fitness of the revised search point
equals the number of significant bit positions that the algorithm has seen when creating it.
For ease of notation, let us assume that f (x̃(t) ) = k. For clarity we emphasize that the
algorithm never learns about the exact fitness value of its original choice x(t) .
Starting from y (0) := x̃(t) , until it reaches a new fitness level > k we allow the algorithm
to remember all queries y (1) , . . . , y (s) , and for each of them whether f (y (i) ) is smaller or
whether it is equal to f (y (0) ) (if f (y (i) ) is larger than f (y (0) ), a new fitness level is reached).
Moreover, we allow it to remember the value k. The algorithm may thus choose y (s+1)
depending on k, y (0) , . . . y (s) , and on the information which of the y (i) have smaller fitness
than y (0) . Crucially, note that in this phase the algorithm does no longer have access to the
positions σ(1), . . . , σ(k) of the first k significant bits, unless it has somehow encoded this
information implicitly, for example in y (0) .
We want to bound from below the expected number of queries that are needed to reach a
new fitness level, that is, the expected number Tm of queries before the algorithm queries a
search point of fitness strictly larger than k = n − m. Note that this number may be zero if
f (x̃(t) ) > k. We shall apply Yao’s MiniMax Principle with the uniform distribution over the
possible Lo instances (z, σ). A discussion of this tool has been given in Section 3.1. We will
show next that, unlike for the original elitist model, in AM every (reasonable) randomized
algorithm is a convex combination of deterministic ones, the crucial difference to the original
elitist model being that in AM the algorithms may remember the search points of the current
fitness level. In particular, a reasonable deterministic algorithm therefore never “gets stuck”.
Formally, we get the following statement.
Lemma 5. Assume that A ∈ AM is a randomized algorithm that never samples a search
point twice on the same fitness level. Then A is a convex combination of deterministic
algorithms in AM .
Before we prove Lemma 5, we recall that a (deterministic or randomized) algorithm
A ∈ AM is allowed to remember all previous queries on the same fitness level, so it will
10

know whether it is about to sample the same search point twice on the same fitness level.
Its runtime can only increase by sampling the same search point twice, so for proving lower
bounds we can restrict to algorithms A as in the lemma. The reason why we actually need
this restriction is that there is only a finite number of possible executions (i.e., of sequences
of queries) of A if we forbid multiple sampling. Otherwise the number of possible executions
would be uncountable, which causes some problems that we want to avoid.
Proof of Lemma 5. Assume we have a randomized algorithm A ∈ AM . All random decisions
of A can be based on a sequence of random coin flips. (Or, depending on the model of
computation, on a sequence of real random variables in the interval [0, 1]. Here we will
assume coin flips.)
For simplicity, we will first argue that for every N > 0, the algorithm A in the phase
before the N-th coin flip can be obtained as a convex combination of (or, more precisely, a
probability distribution over) deterministic algorithms. In other words, if we only consider
the execution of A up to the N-th coin flip, then the randomized algorithm is just a randomly
chosen deterministic one. In the following paragraph we will thus only regard the execution
of A until it requests the N-th coin flip.
We can emulate A as follows. At the very beginning (before actually running A), we
flip nN coins, which we denote by Fi,j , where 1 ≤ i ≤ n runs through all fitness levels, and
1 ≤ j ≤ N. We now run A as follows. When it is on the i-th fitness level and it asks for
the j-th random bit on this fitness level, then we feed it the bit Fi,j . Note that although
there are Nn random bits available in total, A will use at most N of them (in the part of
the execution that we consider).
Now that the Fi,j are fixed, the algorithm A is just a deterministic algorithm. The subtle
point here is that we can also realize it as a deterministic algorithm A in the class AM . This
is because whenever the algorithm A′ is in a specific state (i.e, it has a specific current search
point with specified fitness, and it has some content in the memory that is allowed for the
class AM ), then the available information suffices to determine the number of queries in this
fitness level. In particular, regardless of what A′ has done in previous steps, the current
state is different from all previous states. (This is the crucial difference to the elitist model,
in which a deterministic algorithm may come to the same state twice.) So for all possible
continuations for A in the same state, there is a deterministic algorithm that follows either
continuation. Therefore, once the Fi,j are fixed we can select a deterministic algorithm A
from AM that behaves like A for the first N coin flips.
For unlimited N we use the same argument as before, only that we flip an infinite sequence
of coins for each fitness level. Still, every outcome (Fi,j )1≤i≤n,j≥1 corresponds to exactly one
deterministic algorithm, which also does not query the same search point twice on the same
fitness level. Hence, every such deterministic algorithm is chosen with some probability,
where the probabilities add up to 1. The argument now runs as before.
We show that there is a constant ε > 0 such that for all 1 < m ≤ εn and all deterministic
algorithms in AM the expected number of queries that the algorithm spends on fitness level

11

k = n−m is at least εn. This yields the desired Ω(n2 ) lower bound. By the following lemma,
this bound also holds for all elitist (1 + 1) algorithms.
Lemma 6. Every elitist (1 + 1) algorithm is also in AM .
Proof. This follows rather trivially from the definition of AM . An elitist (1+1) algorithm can
be simulated by an algorithm in AM by choosing x̃(t) := x(t) , and by ignoring all information
except for the current search point. Note that for a (1+1) elitist algorithm it suffices that
the oracle tells it which of the two search points it compares is the better one, or whether
they are of equal fitness. The (1+1) elitist algorithm will thus not know more about the
search points y (i) than whether the fitness is worse, equal, or better than the fitness of y (0) .
Thus the (1+1) elitist algorithm has always at most the information that an algorithm in
AM has.

3.4

It Suffices to Study Single Bit-Flips

One technical challenge in bounding the complexity of Lo with respect to AM is the question
of how to deal with multiple bit flips. The following lemma tells us that we do not give away
much if we restrict ourselves to algorithms that only use one-bit flips. This observation
simplifies the upcoming computations significantly.
Lemma 7. For every deterministic algorithm A ∈ AM there exists a deterministic algorithm
A′ ∈ AM such that the following holds. If for some instance algorithm A uses s queries to
leave fitness level k, then A′ uses at most s + n − k queries on fitness level k. Moreover, all
the search points y ′(1) , . . . , y ′(r) that A′ uses on this fitness level have Hamming distance one
from y (0) .
Proof. Let A ∈ AM be deterministic, and assume it queries y (0) , y (1) , . . . , y (s) on fitness level
k. The algorithm A′ also starts with y (0) . For i ∈ [s] let ℓi ∈ [0..n] be such that y (i) differs
from y (0) in ℓi bits. In the i-th step, which may consist of several queries, A′ goes through
these ℓi bits, flipping them one by one (always starting with y (0) ) and querying the resulting
strings until it finds a string that has fitness smaller than k, or until it has exhausted the ℓi
bits. If A′ creates a string that it queried in one of the previous i − 1 steps, it does not query
this string again. Note that this is possible in the model AM , but would not be possible in
the (1+1) elitist model.
We need to show two things: (i) after each step, A′ has at least as much information as
A has, so that it knows which query y (i+1) algorithm A will choose next, and (ii) A′ uses at
most s + m queries, where m = n − k. In fact, we show that each of the m insignificant bits
causes at most one additional query for A′ . Assume first that A′ exhausts the ℓi bits in step
i, i.e., that all the ℓi corresponding strings have fitness at least k. In this case A learns that
the fitness of y (i) is at least k (and possibly that it is strictly larger than k), and A′ learns
the same. Moreover, A has done one query, while A′ has done one query for each of the at
most ℓi insignificant bits that have not been evaluated before.
Next assume that in the i-th step A′ finds a string that has fitness smaller than k. Say
it is the ℓ′ -th string that A′ queries in the i-th step. Then A only learns that among the
12

ℓi flipped bits there is at least one significant bit. A′ learns this, too, but it also learns
specifically the position of such a bit. Algorithm A uses one query, while A′ uses ℓ′ ≤ ℓi
queries, spending again one query for each insignificant bit that it discovers.
In both cases, algorithm A′ learns at least all the information that A learns, and the total
number of queries done by A′ is at most s + m since it spends at most one query for each
insignificant bit that it tests.
It is now easy to argue that with Lemma 7 at hand we need to consider only algorithms
that do single bit-flips. We show below that, for m being within a suitable range of linear
size, every such algorithm in expectation needs at least m + εn queries to leave fitness level
k := n − m, provided that it started with a search point y (0) of fitness exactly k. Lemma 7
implies that every other algorithm (possibly doing multiple bit-flips) needs in expectation at
least εn queries to leave level k, provided that it visits this level.

3.5

Evolution of the Available Information

In this section we study how the amount of information that a deterministic algorithm has
about the problem instance (z, σ) changes over time, in particular while the algorithm stays
on one fitness level.
Let us consider first how much information the algorithm has when entering a new fitness
level k = n − m. Recall that we consider a problem instance (z, σ) that is taken from all Lo
functions uniformly at random. Remember also that in our model, i.e., model AM described
in Section 3.3, we reveal to the algorithm the value k of the fitness level, the position of the
k significant bits σ(1), . . . , σ(k), and the values zσ(1) , . . . , zσ(k) of the corresponding bits. In
our model AM we allow the algorithm to change the entries in the m insignificant positions.
Intuitively, we thus implicitly grant it m bits for storing information about the problem
instance. In the following, we make this intuition precise.
Let a k-configuration be a pair (P, u) of a subset P of [n] of size k and a {0, 1}-valued
string u of length k. We interpret (P, u) as the set {σ(1), . . . , σ(k)} of the first k significant
bit positions, together with the values zσ(1) , . . . , zσ(k) of these bits in the optimum. Thus a kconfiguration (together with the value of k) describes exactly the information the algorithm
has before choosing the revised search point x̃(t) , when it leaves the (k − 1)-st fitness level.
The (deterministic) algorithm maps each such
 possible k-configuration (P,n u) to a bit string
(t)
k n
x̃ of length n. However, since there are 2 k k-configurations and only 2 bit strings, there


are on average at least 2k−n nk = 2−m k+m
different k-configurations that are matched to
m
(t)
the same string x̃ . In the following, we will track the number C of k-configurations that
are still compatible with the history of the algorithm on level k, i.e., that are compatible
with the fact that f (y (0) ) = k, with the fact that the algorithm has chosen y (0) , and with the
oracle’s answers to y (1) , . . . , y (i) , for some i ≥ 0. Note that Remark 4 applies, i.e., all these
k-configurations are equally likely to be the problem instance.
Assume that the algorithm starts the k-th fitness level with some string y (0) (= x̃(t) ). Then
the compatible k-configurations (P, u) are determined by y (0) and the set P . This follows
from the fact that by construction the entries in the k significant positions in the string y (0)
13

coincide with the optimal ones zσ(1) , . . . , zσ(k) (these bits were not changed when creating
x̃(t) = y (0) ). Since the algorithm has access to y (0) anyway,
compatible
configurations can
 a k+m

n
be described by the k significant positions. There are k = m sets of size k in [n], so it
is convenient to normalize by this factor. We thus define

k+m
B := B(k, m, C) =

m

C

(2)

as the factor by which the number of possible target configurations have been reduced already.
We call B the available information after querying y (i) . Note that always B ≥ 1. We remark
that information is often measured in bits, which would correspond to log B. However, for
our purposes it is more convenient to work with B rather than log B.
Lemma 8. With probability at least 1/2, the available information after querying y (0) is at
most 2m+1 .

Proof. Recall that the algorithm matches on average 2−m k+m
different k-configurations to
m

(t)
(t)
each string x̃ . Let C be the set of all strings x̃ which correspond to at most 2−m−1 k+m

m
k−1 k+m
k-configurations. These strings together cover at most 2n−m−1 k+m
=
2
km
m
configurations, i.e., at most half of all k-configurations. Since the k-configuration of the
problem instance is drawn uniformly at random, with probability at least 1/2 we draw a
configuration that belongs to a string in {0, 1}n \ C. Thus, with probability at least 1/2
we hit a string which is mapped to a x̃(t) that is compatible with more than 2−m−1 k+m
m
k-configurations. This proves the claim.
Let us now consider how the information evolves with the queries on the k-th fitness
level. Let Aone be the set of all deterministic algorithms that, starting from an n-bit string
y (0) with Loz,σ (y (0) ) = k, use only one-bit flips of y (0) until they have found a string y (s) with
Loz,σ (y (s) ) > k.
Definition 9. For any k ≥ 0, m ≥ 1, and B ≥ 1 we define Φ := Φ(k, m, B) to be the
minimal expected number of fitness evaluations that an algorithm A ∈ Aone needs in order to
find the next fitness level on a string with k significant and m insignificant bits if the instance
(z, σ) is chosen uniformly at random among a set C of k-configurations. Here the minimum

is taken over all algorithms A ∈ Aone and all sets C with |C| ≥ C(k, m, B) := k+m
/B. For
m
convenience we set Φ(k, 0, B) := 0 for all k and B.
Note that Φ(k, m, B) is a decreasing function in B. Before we study Φ(k, m, B) in
detail, let us first compare Φ(k, m, B) with the expected time needed by any algorithm in
AM (i.e., not necessarily based on single bit-flips) to reach a new fitness level. When an
algorithm A ∈ AM exceeds fitness k − 1 and chooses x̃(t) , with probability 1/2 it holds that
Loz,σ (x̃(t) ) = k and with probability 1/2 the function value of x̃(t) is strictly larger than
k. This is by the uniform choice of the problem instance. Moreover, by Lemma 8, with
probability at least 1/2 the available information is at most B ≤ 2m+1 , where m = n − k,
and this event is independent of whether Loz,σ (x̃(t) ) = k. In particular, with probability
14

at least 1/4, we have both Loz,σ (x̃(t) ) = k and B ≤ 2m+1 . In this case, by Lemma 7, the
expected time that A spends on the k-th fitness level is at least Φ(k, m, 2m+1 ) − m. Thus,
our aim will be to show that Φ(k, m, 2m+1 ) − m = Ω(n) for a linear number of values of m.
We start our investigations with a recursive formula for Φ.
Lemma 10. Let k ≥ 0, m ≥ 1, and B ≥ 1. Then
Φ(k, m, B) ≥

m+1
.
2

Furthermore, for pmin := max{0, 1 − Bk/(k + m)} and pmax := min{1, Bm/(k + m)} it holds
that



B
m
m−1
(3)
Φ k, m − 1, ·
Φ(k, m, B) ≥ 1 +
min
p
p∈[pmin ,pmax ]
m
p k+m


B
k
+(1 − p)Φ k − 1, m,
,
·
1−p k+m
where we use the convention that for p = 0 (p = 1) the first (second) summand of the
minimum evaluates to zero.
Proof. For the first formula, simply observe that even if the algorithm knows the configuration exactly, it still needs to test the m insignificant bits one by one (by definition of Aone )
until it finds the next significant one, i.e., until the fitness improves. Recalling that the
position of the next significant bit is uniformly among the insignificant ones, the expected
number of steps that it takes the algorithm to find it is (m + 1)/2.
To verify (3), let A ∈ Aone , and assume that the
 set C of configuration compatible with
k+m
(0)
the algorithm’s choice of y satisfies |C| ≥ m /B. We need to show that for each such
A and C the expected number of remaining fitness evaluations to find the next fitness level
is at least the right hand side of (3). Assume further that in its next query, A flips the bit
bi , yielding a search point y (1) , and let p ∈ [0, 1] be such that exactly p|C| configurations
are compatible with the event f (y (1) ) ≥ f (y (0) ). Since all configurations are equally likely, p
(1)
(0)
is also the probability
 that f (y ) ≥ f (y ). Moreover, the number of such configurations
k+m−1
is at most m−1 , since bi has to be one of the insignificant bit positions. This shows


k+m
that p is bounded by the inequality p|C| ≤ k+m−1
.
Using
|C|
≥
/B this implies
m−1
m

k+m−1
p ≤ Bm/(k + m). Similarly, (1 − p)|C| ≤
, which implies p ≥ 1 − Bk/(k + m).
m
(1)
(0)
Assume that the event f (y ) ≥ f (y ) happens. Then with probability 1/m the algorithm leaves the k-th fitness level (since all m insignificant bits have the same probability of being the next significant bit). Otherwise, that is, with probability (m − 1)/m,
the algorithm learns that bi is not the next significant bit, and it will not query bi again
on this level. Therefore, we may just exclude it from our considerations, and replace
m by m − 1. Since the number
is p|C|, we need
 of remaining compatible configurations

k+m
to find Bnew such that k+m−1
/B
≤
p|C|.
Since
p|C|
≥
p
/B,
we may choose
new
m
 m−1

k+m−1
k+m
Bnew to satisfy m−1 /Bnew = p m /B, or equivalently Bnew = (B/p) · (m/(k + m)).
15

So if 
f (y (1) ) ≥ f (y (0) ) 
then the algorithm needs at least an expected additional time of
m−1
B
m
Φ k, m − 1, p · k+m .
m

Now we consider the case f (y (1) ) < f (y (0) ), which happens with probability 1 − p. Then
the algorithm learns that bi is significant, and it will not query bi again on this level. Thus
we can exclude it from our considerations and replace k by k − 1. Similar as before, the
number of compatible configurations drops to (1 − p)|C|, so we need to find Bnew such
that

k+m−1
k+m−1
/B
≤
(1
−
p)|C|.
We
may
choose
B
according
to
the
equation
/B
new
new
new =
m
m

k+m
(1)
(0)
(1 − p) m /B and obtain Bnew = (B/(1 − p)) · (k/(k + m)). So if f (y ) < f (y ) then the
algorithm needs at least an expected additional time of Φ(k − 1, m, B/(1 − p) · k/(k + m)).
This proves (3).
We use Lemma 10 to show the following lower bound for Φ(k, m, B). Once this bound is
proven, we have everything together to prove the claimed Ω(n2 ) bound for the (1+1) elitist
black-box complexity of Lo.
Lemma 11. There exists a constant ε > 0 such that for all k ≥ 0, m ≥ 1 and B ≥ 1,


log B
Φ(k, m, B) ≥ ε(k + m) 1 −
.
2m

(4)

Proof. We use induction on k + m. First we show the statement for the case m = 1 and
arbitrary k. If m = 1 and B ≥ 4, the lower bound is at most zero, and thus trivial. If m = 1
and B < 4, by (2), the number of compatible configurations is at least (k + 1)/B > (k + 1)/4,
and in each of these configurations there is exactly one insignificant bit. Since these bits are
all different from each other, there are at least (k + 1)/4 positions at which the insignificant
bit might be, and by Remark 4 all these positions are equally likely. Since the algorithm is
by definition only allowed to make one-bit flips, it needs in expectation at least (k + 1)/8
steps. Thus, the statement is satisfied for all ε ≤ 1/8.
Now we come to the inductive step, where by the paragraph above we may assume that
m ≥ 2. Furthermore, we may also assume that log B < 2m since the statement is trivial
otherwise. By Lemma 10 we have



m−1
B
m
Φ(k, m, B) ≥ 1 + min
(5)
p
Φ k, m − 1, ·
p∈[pmin,pmax ]
m
p k+m


B
k
+ (1 − p) · Φ k − 1, m,
.
·
1−p k+m

16

By the induction hypothesis we may thus conclude from inequality (5) that
(
m
)
log( Bp · k+m
m−1
Φ(k, m, B) ≥ 1 + min
p
ε(k + m − 1) 1 −
p∈[pmin ,pmax ]
m
2(m − 1)
+(1 − p)ε(k + m − 1) 1 −

B
·
log( 1−p



log B
= 1 + ε(k + m) 1 −
+
min
{−R(p)} ,
p∈[pmin,pmax ]
2m

2m

k
)
k+m 

)

where R(p) equals
R(p) =
+
+
+
+
+
+

m
log Bp · k+m
1
pε(k + m − 1) 1 −
m
2(m − 1)
!

m
log Bp · k+m
pε 1 −
2(m − 1)

m
log 1p · k+m
pε(k + m)
2m
m
)
log( 1p · k+m
pε(k + m)
2m(m − 1)
log B
pε(k + m)
2m(m − 1)
!
B
k
log( 1−p
· k+m
)
(1 − p)ε 1 −
2m

(1 − p)ε(k + m)

1
·
log( 1−p

k
)
k+m

2m

!

=: X1
=: A1
=: Y1
=: Z
=: X2
=: A2
=: Y2

The above expression for R(p) can be verified by elementary calculations, using only that
log(Bx) = log B + log x for x = 1/p · m/(k + m) and for x = 1/(1 − p) · k/(k + m). It thus
suffices to show that
R(p) ≤ 1 for all p ∈ [pmin, pmax ].

(6)

m
B
k
To this end we first observe that Bp · k+m
≥ 1 and 1−p
· k+m
≥ 1 by definition of pmin and
pmax . Since these expressions occur X1 , A1 , and A2 , we get

A1 + A2 ≤ ε.

(7)

For the same reason, X1 ≤ pε(k + m − 1)/m. Recalling log B < 2m and using m − 1 ≥ m/2,
we thus get
X1 + X2 ≤ 3pε(k + m)/m =: X
(8)
17

In the following we will show that Y1 + Y2 + X + Z ≤ 1/2 if ε is sufficiently small. Together
with (7) and (8), this will complete the inductive step.
Let p0 := m/(k + m), and write p = γp0 for some (not necessarily constant) γ ≥ 0. Note
that X = 3γε. We first consider the case γ ≤ 2. In this case, X ≤ 6ε. Moreover, Z is either
negative (for γ > 1) or upper bounded by −εγ log γ ≤ ε/(e ln 2), since the function −γ log γ
has a unique maximum 1/(e ln 2) in the interval 0 < γ ≤ 1. Either way, we can choose ε so
small that X + Z ≤ 1/2. In the following we will prove that Y1 + Y2 ≤ 0, which will settle
the case γ ≤ 2.
To prove that Y1 + Y2 is non-positive, we may as well consider the sign of the function


 
1 − p0
p0
2m
+ (1 − p) log
.
(Y1 + Y2 ) = p log
f (p) :=
(k + m)ε
p
1−p
The function has derivatives
′

f (p) = log



p0
p



− log



1 − p0
1−p



and

1
< 0.
p(1 − p) ln(2)
Since the second derivative is negative, the function f is concave. We further observe that
f (p0 ) = f ′ (p0 ) = 0. Thus f has a unique maximum at p = p0 . Therefore, f (p) ≤ f (p0 ) = 0
for all 0 ≤ p ≤ 1. Hence, we have proven Y1 + Y2 ≤ 0, and this concludes the case γ ≤ 2.
For the case γ > 2, we first show that Y1 /2 + X + Z ≤ 1/2. Clearly we have Z ≤ 0. For
sufficiently small ε > 0 we obtain


1024ε
εγ log γ
log γ
Y1
≤
+X =−
+ 3εγ = εγ 3 −
≤ 1/2,
2
4
4
e ln 2
f ′′ (p) = −

where the second to last inequality can be easily checked by taking the derivative of the
function and observing that is has a global maximum for γ = 4096/e.
Next we show that Y1 /2 + Y2 ≤ 0 for all γ > 2. Similar as before, we may consider the
sign of the function


 
2m
1
−
p
p
p
0
0
f˜(p) :=
+ (1 − p) log
(Y1 /2 + Y2 ) = log
(k + m)ε
2
p
1−p
under the additional constraint 2p0 < p ≤ 1. Similar as above, the second derivative of f˜ for
0 < p < 1 is
(p + 1)
< 0.
f˜′′ (p) = −
2 ln(2)p(1 − p)
Thus f˜ is concave for 0 ≤ p ≤ 1. Recall that log(1 + x) < x for all x > 0. Therefore,


p0
˜
f (2p0 ) = −p0 log(2) + (1 − 2p0 ) log 1 +
< −p0 + p0 = 0.
1 − 2p0
18

On the other hand, f˜(p0 ) = 0 > f˜(2p0 ). Since f˜ is concave, this implies f˜(p) < 0 for all
2p0 < p < 1. This shows that Y1 /2 + Y2 ≤ 0 for all γ > 2.
Summarizing, we have shown that Y1 /2 + Y2 ≤ 0 and Y1 /2 + X + Z ≤ 1/2 for all γ > 2.
Together with (7) and (8), this concludes the inductive step and the proof.

3.6

Putting Everything Together

As outlined in the high-level overview, Lemma 7, 8, and 11 together imply runtime Ω(n2 ) on
the Lo problem for any algorithm in AM . More precisely, we obtain the following theorem.
Theorem 12. With ε as in Lemma 11 and k satisfying 1 < n − k ≤ εn/8, every algorithm
A ∈ AM spends in expectation at least εn/32 function evaluations on level k, and this
lower bound holds independently of the time spent on previous levels. In particular, every
algorithm in AM (and thus, every elitist (1+1) black-box algorithm) needs at least time Ω(n2 )
in expectation and with high probability.
Proof. We have already argued above after Definition 9 that each deterministic algorithm
A ∈ AM spends in expectation at least time (Φ(k, m, 2m+1 )−m)/4 on fitness level k = n−m,
since with probability 1/2 the algorithm does not skip the level, with probability 1/2 the
available information is at most 2m+1 (Lemma 8), and conditioned on both these events, by
Lemma 7, A spends at least expected time Φ(k, m, 2m+1 ) − m on the k-th fitness level. By
Lemma 5 we may apply Yao’s principle to deduce that the same bound also holds for every
randomized algorithm A ∈ AM .
The lower bound follows immediately from Lemma 11 which for k and m satisfying
1 < m = n − k ≤ εn/8 yields


m+1
εn εn
εn
m+1
Φ(k, m, 2
) − m ≥ εn 1 −
−m≥
−
=
.
2m
4
8
8
Note that this lower bound holds independently of the time spent on other fitness levels
because in the model M every algorithm which enters the k-th fitness level is in exactly the
same state, i.e., it has access to exactly the same information, independent of its history.
Since the lower bound holds for all algorithms in AM , it still holds if we condition on the
history of the algorithm, or specifically on the time spent on previous fitness levels.
The lower bound Ω(n2 ) on the expected runtime follows immediately. For the statement
with high probability, it follows by a mostly formal argument that every algorithm spends at
least linear time on each level with probability Ω(1). Note that this implies the statement,
since then by the Chernoff bound with high probability every algorithm spends at least
linear time on a linear number of levels. Since the formal argument is somewhat tricky, we
elaborate on it.
We want to show that there are constants c, p > 0 such that for sufficiently large n, every
algorithm in AM spends at least time cn with probability at least p on level k. Assume
otherwise for the sake of contradiction, so assume that for every constant c, p > 0 there is an
algorithm A ∈ AM and there are arbitrarily large n such that A spends at least time cn with
19

probability at most p. Then as a formal consequence the same holds for c, p = o(1), so there
are functions c = c(n) = o(1) and p = p(n) = o(1) such that there is an algorithm A ∈ AM
and arbitrarily large n for which A spends at least time cn with probability at most p. Fix
such an algorithm A, and consider the algorithm A′ ∈ AM that behaves like A for the first
cn queries, and afterwards just does random single bit flips. Note that the latter strategy
takes expected time at most n to leave fitness level k. Therefore, A′ needs in expectation at
most cn + pn = o(n) queries to leave level k (for arbitrarily large values of n), contradicting
the fact that every algorithms in A needs expected time Ω(n). This concludes the formal
argument, and thus the proof.
Remark 13. Theorem 12 can be strengthened in the following way. Assume that an elitist
(1 + 1) algorithm has an additional memory of size ε′ n which it may use without restrictions.
Then if ε′ is sufficiently small, the algorithm still has expected runtime Ω(n2 ).
On the other hand, if the algorithm has in addition n + O(log n) bits of memory that it
may use without restriction, then it is possible to achieve a runtime of O(n log n). Hence, if
the algorithm has access to cn bits of unrestricted memory, then it depends on the constant
c whether runtime o(n2 ) is possible or not.
Proof. The proof of the first statement is identical to the proof of Theorem 12, except that
′
we increase the available information B by a factor 2ε n . E.g., for ε′ = ε/16 the algorithm
still spends an expected linear time on all levels with εn/12 ≤ m ≤ εn/8.
The second statement holds because it is possible to store all k significant bits in n bits
of the additional memory, and the remaining O(log n) bits may serve as a counter. Then,
whenever the fitness increases, the algorithm performs O(log n) steps to determine (one of)
the position(s) which was responsible for the improvement. The details are as follows.
We split the additional memory into a block B1 of length n, and the remaining part B2 .
Let x denote the current search point, and let ℓ be the current number of one-bits in B1 . We
maintain the invariant that every one-bit in B1 is at the position of one of the f (x) leading
bits. Note that this implies that every such position must be correct in x. At start we choose
B1 to be the all-zero string.
We iteratively proceed as follows. If ℓ = f (x), then the bits in B1 correspond exactly to
the first f (x) leading bits. In this case we flip all positions in x that correspond to zero-bits
in B1 , and this operation improves the fitness of x by at least one. In the same operation,
we (re-)set B2 to zero. On the other hand, assume ℓ 6= f (x). Then our invariant implies
ℓ < f (x). Let us call P the set of all bit positions that are correct in x but are not one-bits
in B1 . Our aim is to identify one of the f (x) − ℓ positions in P . Let P0 be the set of positions
of zero-bits in B1 . In our strategy P0 will serve as a set of candidate positions, which we will
shrink iteratively. We create a search point x′ by flipping the first half of the positions P0
in x, and query f (x′ ). If f (x′ ) > f (x) then we (have to) accept the new search point, and
we reset all of B2 to zero. If f (x′ ) < f (x) then we know that at least one of the positions
in P lies in the first half of P0 , so we replace P0 by its first half, and encode this result by a
single bit in B2 . Finally, if f (x′ ) = f (x) then at least one (in fact, all) of the positions in P
lie in the second half of P0 , so we replace P0 by its second half, and also encode this result
by a single bit in B2 . Repeating this step, we iteratively decrease the size of P0 by a factor
20

of 2, or find a better search point. We continue this procedure for at most ⌈log n⌉ rounds,
after which we have either found a better search point, or reduced P0 to a single position,
which then must be a position in P . In the latter case, we flip the corresponding bit in B1
to one, reset B2 to zero, and continue.
In this way, in log n steps, we can increase either the fitness of x, or the number of ones in
B1 . Since we never flip any bit in B1 to zero, after O(n log n) steps, either f (x) = n or B1 is
the all-one string. By the invariant the latter also implies f (x) = n, so the algorithm finds
the optimum after O(n log n) steps.

4

Conclusions and Outlook

We have shown that the (1+1) elitist black-box complexity of Lo is Θ(n2 ). This is in contrast
to the situation for the OneMax function, where elitist selection does not substantially harm
the running time [DL15b]. Given the much smaller complexity of Lo in many other models,
this sheds some light on the cost of elitism. In fact, our proof suggests that the reason for
the large complexity is rather the memory restriction than the selection strategy. We thus
conjecture that the lower bound in Theorem 1 holds already for (1+1) memory-restricted
algorithms, but we do not see at the moment a feasible proof for this claim. In particular
the generalization of Lemma 7, i.e., the statement that it suffices to consider one-bit flips,
seems tricky.
Our methods are adapted to the Lo problem, and it is probably non-trivial to transfer
them to other problems. Nevertheless, we are optimistic that the similar approaches can
work both for other black-box complexities and other function classes.
Finally, in light of [DDE13] we are interested to use the insights from our investigations
for the design of new search heuristics.

Acknowledgments
This research benefited from the support of the “FMJH Program Gaspard Monge in optimization and operation research”, and from the support to this program from Électricité de
France.

References
[AAD+ 13] Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr,
Kasper Green Larsen, and Kurt Mehlhorn. The query complexity of finding
a hidden permutation. In Space-Efficient Data Structures, Streams, and Algorithms - Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday,
volume 8066 of Lecture Notes in Computer Science, pages 1–11. Springer, 2013.

21

[BDN10]

S. Böttcher, B. Doerr, and F. Neumann. Optimal fixed and adaptive mutation
rates for the LeadingOnes problem. In Proc. of the 11th International Conference
on Parallel Problem Solving from Nature (PPSN’10), pages 1–10. Springer, 2010.

[DDE13]

Benjamin Doerr, Carola Doerr, and Franziska Ebel. Lessons from the black-box:
Fast crossover-based genetic algorithms. In Proc. of Genetic and Evolutionary
Computation Conference (GECCO’13), pages 781–788. ACM, 2013.

[DJK+ 11] Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Per Kristian Lehre, Markus
Wagner, and Carola Winzen. Faster black-box algorithms through higher arity
operators. In Proc. of Foundations of Genetic Algorithms (FOGA’11), pages
163–172. ACM, 2011.
[DJW02]

Stefan Droste, Thomas Jansen, and Ingo Wegener. On the analysis of the (1+1)
evolutionary algorithm. Theoretical Computer Science, 276:51–81, 2002.

[DJW06]

Stefan Droste, Thomas Jansen, and Ingo Wegener. Upper and lower bounds for
randomized search heuristics in black-box optimization. Theory of Computing
Systems, 39:525–544, 2006.

[DL15a]

Carola Doerr and Johannes Lengler. Elitist black-box models: Analyzing the
impact of elitist selection on the performance of evolutionary algorithms. In
Proc. of Genetic and Evolutionary Computation Conference (GECCO’15), pages
839–846, 2015.

[DL15b]

Carola Doerr and Johannes Lengler. OneMax in black-box models with several restrictions. In Proc. of Genetic and Evolutionary Computation Conference
(GECCO’15), pages 1431–1438, 2015.

[DW12]

Benjamin Doerr and Carola Winzen. Black-box complexity: Breaking the
O(n log n) barrier of LeadingOnes. In Artificial Evolution (EA’11), Revised Selected Papers, volume 7401 of Lecture Notes in Computer Science, pages 205–216.
Springer, 2012.

[DW14a]

Benjamin Doerr and Carola Winzen. Playing Mastermind with constant-size
memory. Theory of Computing Systems, 55:658–684, 2014.

[DW14b]

Benjamin Doerr and Carola Winzen. Ranking-based black-box complexity. Algorithmica, 68:571–609, 2014.

[Lad05]

Véronique Ladret. Asymptotic hitting time for a simple evolutionary model of
protein folding. Journal of Applied Probability, 42:39–51, 2005.

[LW12]

Per Kristian Lehre and Carsten Witt. Black-box search by unbiased variation.
Algorithmica, 64:623–642, 2012.

22

[MR95]

Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge
University Press, 1995.

[Müh92]

Heinz Mühlenbein. How genetic algorithms really work: Mutation and hillclimbing. In Proc. of the 2nd International Conference on Parallel Problem Solving
from Nature (PPSN’92), pages 15–26. Elsevier, 1992.

[Rud97]

Günter Rudolph. Convergence Properties of Evolutionary Algorithms. Kovac,
1997.

[Sud13]

Dirk Sudholt. A new method for lower bounds on the running time of evolutionary
algorithms. IEEE Transactions on Evolutionary Computation, 17:418–435, 2013.

[Yao77]

Andrew Chi-Chin Yao. Probabilistic computations: Toward a unified measure
of complexity. In Proc. of Foundations of Computer Science (FOCS’77), pages
222–227. IEEE, 1977.

23

