  We argue that proven exponential upper bounds on runtimes, an established
area in classic algorithms, are interesting also in heuristic search and we
prove several such results. We show that any of the algorithms randomized local
search, Metropolis algorithm, simulated annealing, and (1+1) evolutionary
algorithm can optimize any pseudo-Boolean weakly monotonic function under a
large set of noise assumptions in a runtime that is at most exponential in the
problem dimension~$n$. This drastically extends a previous such result, limited
to the (1+1) EA, the LeadingOnes function, and one-bit or bit-wise prior noise
with noise probability at most $1/2$, and at the same time simplifies its
proof. With the same general argument, among others, we also derive a
sub-exponential upper bound for the runtime of the $(1,\lambda)$ evolutionary
algorithm on the OneMax problem when the offspring population size $\lambda$ is
logarithmic, but below the efficiency threshold. To show that our approach can
also deal with non-trivial parent population sizes, we prove an exponential
upper bound for the runtime of the mutation-based version of the simple genetic
algorithm on the OneMax benchmark, matching a known exponential lower bound.
