Asymptotic behavior of the numbers of runs and microruns

The notion of run (also called maximal repetition) allows a compact representation of the set of all tandem periodicities, even fractional, in a string. Since the work of Kolpakov and Kucherov, it is known that ρ(n), the maximum number of runs in a string, is linear in the length n of the string. Lower bounds haven been provided by Franek et al. and Matsubara et al. (0.944n) and upper bounds have been provided by Rytter, Puglisi et al., and Crochemore and Ilie (1.048n). However, very few properties are known for the ρ(n)/n function. We show here by a simple argument that limn↦∞ρ(n)/n exists and that this limit is never reached. We further study the asymptotic behavior of ρp(n), the maximal number of runs with period at most p. Finally, we provide the first exact limits for some microruns. For example, we have limn↦∞ρ14(n)/n=15/17.