  Quality diversity~(QD) is a branch of evolutionary computation that gained
increasing interest in recent years. The Map-Elites QD approach defines a
feature space, i.e., a partition of the search space, and stores the best
solution for each cell of this space. We study a simple QD algorithm in the
context of pseudo-Boolean optimisation on the ``number of ones'' feature space,
where the $i$th cell stores the best solution amongst those with a number of
ones in $[(i-1)k, ik-1]$. Here $k$ is a granularity parameter $1 \leq k \leq
n+1$. We give a tight bound on the expected time until all cells are covered
for arbitrary fitness functions and for all $k$ and analyse the expected
optimisation time of QD on \textsc{OneMax} and other problems whose structure
aligns favourably with the feature space. On combinatorial problems we show
that QD finds a ${(1-1/e)}$-approximation when maximising any monotone
sub-modular function with a single uniform cardinality constraint efficiently.
Defining the feature space as the number of connected components of a connected
graph, we show that QD finds a minimum spanning tree in expected polynomial
time.
