# Asymptotics of Divide-And-Conquer Recurrences Via Iterated Function Systems

Abstract : Let $k≥2$ be a fixed integer. Given a bounded sequence of real numbers $(a_n:n≥k)$, then for any sequence $(f_n:n≥1)$ of real numbers satisfying the divide-and-conquer recurrence $f_n = (k-mod(n,k))f_⌊n/k⌋+mod(n,k)f_⌈n/k⌉ + a_n, n ≥k$, there is a unique continuous periodic function $f^*:\mathbb{R}→\mathbb{R}$ with period 1 such that $f_n = nf^*(\log _kn)+o(n)$. If $(a_n)$ is periodic with period $k, a_k=0$, and the initial conditions $(f_i:1 ≤i ≤k-1)$ are all zero, we obtain a specific iterated function system $S$, consisting of $k$ continuous functions from $[0,1]×\mathbb{R}$ into itself, such that the attractor of $S$ is $\{(x,f^*(x)): 0 ≤x ≤1\}$. Using the system $S$, an accurate plot of $f^*$ can be rapidly obtained.
Keywords :
Type de document :
Communication dans un congrès
Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.55-66, 2012, DMTCS Proceedings
Domaine :

Littérature citée [6 références]

https://hal.inria.fr/hal-01197237
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 11 septembre 2015 - 12:54:59
Dernière modification le : mardi 7 mars 2017 - 15:18:27
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:34:53

### Fichier

dmAQ0105.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01197237, version 1

### Citation

John Kieffer. Asymptotics of Divide-And-Conquer Recurrences Via Iterated Function Systems. Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.55-66, 2012, DMTCS Proceedings. 〈hal-01197237〉

### Métriques

Consultations de la notice

## 176

Téléchargements de fichiers