We give a detailed analysis of the optimization time of the [Formula: see text]-Evolutionary Algorithm under two simple fitness functions (OneMax and LeadingOnes). The problem has been approached in the evolutionary algorithm literature in various ways and with different degrees of rigor. Our asymptotic approximations for the mean and the variance represent the strongest of their kind. The approach we develop is based on an asymptotic resolution of the underlying recurrences and can also be extended to characterize the corresponding limiting distributions. While most of our approximations can be derived by simple heuristic calculations based on the idea of matched asymptotics, the rigorous justifications are challenging and require a delicate error analysis.

Range Quickselect, a simple modification of the well-known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Range Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm.The key element appearing in the analysis of Range Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us.In particular, we have been able to carry out a precise analysis of the expected number of moves of the pth element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results.Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.

We study the variety of subtrees lying on the fringe of recursive trees and binary search trees by analyzing the distributional behavior of $X_{n,k}$, which counts the number of subtrees of size k in a random tree of size n, with $k = k(n)$ dependent on n. Using analytic methods we can characterize for both tree families the phase change behavior of $X_{n,k}$ as follows. In the subcritical case, when $k(n)/\sqrt{n} \to 0$, we show that $X_{n,k}$ is (after normalization) asymptotically normally distributed, whereas in the supercritical case, when $k(n)/\sqrt n \to \infty$, $X_{n,k}$ converges to 0. In the critical case, when $k(n) = \Theta(\sqrt{n}\,)$, we show that if $k/\sqrt{n}$ approaches a limit, then $X_{n,k}$ converges in distribution to a Poisson random variable, whereas if $k/\sqrt{n}$ does not approach a finite nonzero limit, the size oscillates and does not converge in distribution to any random variable. In regard to recursive trees and binary search trees, this provides an understanding of the complete spectrum of phases of $X_{n,k}$ and the gradual change from the subcritical to the supercritical phase.

For the analysis of an algorithm to generate binary trees, the behaviour of a certain sequence of numbers is essential. In the original paper, it was expressed by a recursion. Here, we show how to solve this (and similar) recursions, both explicitly and asymptotically. Some additional information about useful mathematical software is also provided.