This paper traces early historical developments of analytic combinatorics through a single object: the finite difference Δ^k 0ⁿ (the ordered Stirling numbers). We examine how Laplace transformed this discrete quantity into real integral representations to derive saddle-point approximations, establishing an early encoding-integration-approximation pipeline. Cauchy’s 1815 memoir then moved the same problem toward complex-analytic territory. Through this narrative we illustrate a pivotal transition: from an eighteenth-century algebra of formal identities to a nineteenth-century discipline of ε-δ inequalities.

The expected running time of the classical (1+1) EA on the ONEMAX benchmark function has recently been determined by Hwang et al. (2018) up to additive errors of O((log n)/n). The same approach proposed there also leads to a full asymptotic expansion with errors of the form O(n-K log n) for any K > 0. This precise result is obtained by matched asymptotics with rigorous error analysis (or by solving asymptotically the underlying recurrences via inductive approximation arguments), ideas radically different from well-established techniques for the running time analysis of evolutionary computation such as drift analysis. This paper revisits drift analysis for the (1+1) EA on ONE MAX and obtains that the expected running time E (T), starting from [n/2] one-bits, is determined by the sum of inverse drifts up to logarithmic error terms, more precisely

We consider random rooted maps without regard to their genus, with fixed large number of edges, and address the problem of limiting distributions for six different parameters: vertices, leaves, loops, root edges, root isthmus, and root vertex degree. Each of these leads to a different limiting distribution, varying from (discrete) geometric and Poisson distributions to different continuous ones: Beta, normal, uniform, and an unusual distribution whose moments are characterised by a recursive triangular array.

Asymptotic expansions for the Taylor coefficients of the Lagrangean form phi(z)=zf(phi(z)) are examined with a focus on the calculations of the asymptotic coefficients. The expansions are simple and useful, and we discuss their use in some enumerating sequences in trees, lattice paths and planar maps.

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.

Several simple, classical, little-known algorithms in the statistics and computer science literature for generating random permutations by coin tossing are examined, analyzed, and implemented. These algorithms are either asymptotically optimal or close to being so in terms of the expected number of times the random bits are generated. In addition to asymptotic approximations to the expected complexity, we also clarify the corresponding variances, as well as the asymptotic distributions. A brief comparative discussion with numerical computations in a multicore system is also given.

Divide-and-conquer recurrences of the form f ( n ) = f (⌊ n/2⌋ ) + f ( ⌈ n/2⌉ ) + g ( n ) ( n ⩾ 2), with g ( n ) and f (1) given, appear very frequently in the analysis of computer algorithms and related areas. While most previous methods and results focus on simpler crude approximation to the solution, we show that the solution always satisfies the simple identity f ( n ) = n P (log 2 n ) − Q ( n ) under an optimum (iff) condition on g ( n ). This form is not only an identity but also an asymptotic expansion because Q ( n ) is of a smaller order than linearity. Explicit forms for the continuous periodic function P are provided. We show how our results can be easily applied to many dozens of concrete examples collected from the literature and how they can be extended in various directions. Our method of proof is surprisingly simple and elementary but leads to the strongest types of results for all examples to which our theory applies.

We analyze the cost used by a naive exhaustive search algorithm for finding a maximum independent set in random graphs under the usual $\mathscr{G}_{n,p}$-model where each possible edge appears independently with the same probability $p$. The expected cost turns out to be of the less common asymptotic order $n^{c\log n}$, which we explore from several different perspectives. Also we collect many instances where such an order appears, from algorithmics to analysis, from probability to algebra. The limiting distribution of the cost required by the algorithm under a purely idealized random model is proved to be normal. The approach we develop is of some generality and is amenable for other graph algorithms.

Skylines emerged as a useful notion in database queries for selecting representative groups in multivariate data samples for further decision making, multiobjective optimization, or data processing, and the $k$-dominant skylines were naturally introduced to resolve the abundance of skylines when the dimensionality grows or when the coordinates are negatively correlated. We prove in this paper that the expected number of $k$-dominant skylines is asymptotically zero for large samples when $1\leq k\leq d-1$ under two reasonable (continuous) probability assumptions of the input points, $d$ being the (finite) dimensionality, in contrast to the asymptotic unboundedness when $k=d$. In addition to such an asymptotic zero-infinity property, we also establish a sharp threshold phenomenon for the expected $(d-1)$-dominant skylines when the dimensionality is allowed to grow with $n$, the sample size. Several related issues, such as the dominant cycle structures, the numerical aspects, and the practical implications, are also briefly studied.

Tries (from retrieval) are one of the most popular data structures on words. They are pertinent to the (internal) structure of stored words and several splitting procedures used in diverse contexts. The profile of a trie is a parameter that represents the number of nodes (either internal or external) with the same distance from the root. It is a function of the number of strings stored in a trie and the distance from the root. Several, if not all, trie parameters such as height, size, depth, shortest path, and fill-up level can be uniformly analyzed through the (external and internal) profiles. Although profiles represent one of the most fundamental parameters of tries, they have hardly been studied in the past. The analysis of profiles is surprisingly arduous, but once it is carried out it reveals unusually intriguing and interesting behavior. We present a detailed study of the distribution of the profiles in a trie built over random strings generated by a memoryless source. We first derive recurrences satisfied by the expected profiles and solve them asymptotically for all possible ranges of the distance from the root. It appears that profiles of tries exhibit several fascinating phenomena. When moving from the root to the leaves of a trie, the growth of the expected profiles varies. Near the root, the external profiles tend to zero at an exponential rate, and then the rate gradually rises to being logarithmic; the external profiles then abruptly tend to infinity, first logarithmically and then polynomially; they then tend polynomially to zero again. Furthermore, the expected profiles of asymmetric tries are oscillating in a range where profiles grow polynomially, while symmetric tries are nonoscillating, in contrast to most shape parameters of random tries studied previously. Such a periodic behavior for asymmetric tries implies that the depth satisfies a central limit theorem but not a local limit theorem of the usual form. Also the widest levels in symmetric tries contain a linear number of nodes, differing from the order $n/\sqrt{\log n}$ for asymmetric tries, n being the size of the trees. Finally, it is observed that profiles satisfy central limit theorems when the variance goes unbounded, while near the height they are distributed according to Poisson laws. As a consequence of these results we find typical behaviors of the height, shortest path, fill-up level, and depth. These results are derived here by methods of analytic algorithmics such as generating functions, Mellin transform, Poissonization and de-Poissonization, the saddle-point method, singularity analysis, and uniform asymptotic analysis.

We show that a wide class of linear cost measures (such as the number of leaves) in random d -dimensional point quadtrees undergo a change in limit laws: If the dimension d = 1, …, 8, then the limit law is normal; if d ≥ 9 then there is no convergence to a fixed limit law. Stronger approximation results such as convergence rates and local limit theorems are also derived for the number of leaves, additional phase changes being unveiled. Our approach is new and very general, and also applicable to other classes of search trees. A brief discussion of Devroye's grid trees (covering m -ary search trees and quadtrees as special cases) is given. We also propose an efficient numerical procedure for computing the constants involved to high precision.

We solve the open problem of characterizing the leading constant in the asymptotic approximation to the expected cost used for random partial match queries in random k-d trees. Our approach is new and of some generality; in particular, it is applicable to many problems involving differential equations (or difference equations) with polynomial coefficients.

We show that the variances of the profile (number of nodes at each level) of random binary search trees undergoes asymptotically four phase transitions and exhibits a bimodal or "two-humped" behavior, in contrast to the unimodality of the expected value of the profiles. Precise asymptotic approximations are derived. The same types of phenomena also hold for the profile of random recursive trees.

We propose a simple direct approach for computing the expected cost of random partial match queries in random quadtrees. This approach gives not only an explicit expression for the leading constant in the asymptotic approximation of the expected cost but also more terms in the asymptotic expansion if desired.

Redundancy is defined as the excess of the code length over the optimal (ideal) code length. We study the average redundancy of an idealized arithmetic coding (for memoryless sources with unknown distributions) in which the Krichevsky and Trofimov (1981) estimator is followed by the Shannon-Fano code. We shall ignore here important practical implementation issues such as finite precisions and finite buffer sizes. In fact, our idealized arithmetic code can be viewed as an adaptive infinite precision implementation of arithmetic encoder that resembles Elias coding. However, we provide very precise results for the average redundancy that takes into account integer-length constraints. These findings are obtained by analytic methods of analysis of algorithms such as theory of distribution of sequences modulo 1 and Fourier series. These estimates can be used to study the average redundancy of codes for tree sources, and ultimately the context-tree weighting algorithms.

We characterize all limit laws of the quicksort-type random variables defined recursively by ${\cal L}(X_n)= {\cal L}(X_{I_n}+X^*_{n-1-I_n}+T_n)$ when the "toll function" T n varies and satisfies general conditions, where (X n ), (X n * ), (I n , T n ) are independent, I n is uniformly distributed over {0, . . .,n-1}, and ${\cal L}(X_n)={\cal L}(X_n^\ast)$. When the "toll function" T n (cost needed to partition the original problem into smaller subproblems) is small (roughly $\limsup_{n\rightarrow\infty}\log E(T_n)/\log n\le 1/2$), X n is asymptotically normally distributed; nonnormal limit laws emerge when T n becomes larger. We give many new examples ranging from the number of exchanges in quicksort to sorting on a broadcast communication model, from an in-situ permutation algorithm to tree traversal algorithms, etc.

Two algorithms for inserting a random element into a random heap are shown to be optimal (in the sense that they use the least number of comparisons on the average among all comparison-based algorithms) for different values of n under a uniform model.