https://hal.inria.fr/hal-01197237Kieffer, JohnJohnKiefferECE - Department of Electrical and Computer Engineering [Minneapolis] - UMN - University of Minnesota [Twin Cities] - University of Minnesota SystemAsymptotics of Divide-And-Conquer Recurrences Via Iterated Function SystemsHAL CCSD2012divide-and-conquer recurrencesiterated function systemsIFS attractorself-affine functions[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS][INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM][MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO][INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]Episciences Iam, CoordinationBroutin, Nicolas and Devroye, Luc2015-09-11 12:54:592021-02-27 16:02:052015-09-11 13:33:27enConference papershttps://hal.inria.fr/hal-01197237/document10.46298/dmtcs.2983application/pdf1Let \$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.