John Kieffer
-
Asymptotics of Divide-And-Conquer Recurrences Via Iterated Function Systems
dmtcs:2983 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2012,
DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
-
https://doi.org/10.46298/dmtcs.2983
Asymptotics of Divide-And-Conquer Recurrences Via Iterated Function SystemsConference paper
Authors: John Kieffer 1
NULL
John Kieffer
1 Department of Electrical and Computer Engineering [Minneapolis]
Let k≥2 be a fixed integer. Given a bounded sequence of real numbers (an:n≥k), then for any sequence (fn:n≥1) of real numbers satisfying the divide-and-conquer recurrence fn=(k−mod(n,k))f⌊n/k⌋+mod(n,k)f⌈n/k⌉+an,n≥k, there is a unique continuous periodic function f∗:R→R with period 1 such that fn=nf∗(logkn)+o(n). If (an) is periodic with period k,ak=0, and the initial conditions (fi:1≤i≤k−1) are all zero, we obtain a specific iterated function system S, consisting of k continuous functions from [0,1]×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.
Volume: DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
Collaborative Research: Information Theory of Data Structures; Funder: National Science Foundation; Code: 0830457
Bibliographic References
2 Documents citing this article
Hsien-Kuei Hwang;Svante Janson;Tsung-Hsi Tsai, 2017, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half, ACM Transactions on Algorithms, 13, 4, pp. 1-43, 10.1145/3127585.
Jie Zhang;En-Hui Yang;John C. Kieffer, 2014, A Universal Grammar-Based Code for Lossless Compression of Binary Trees, arXiv (Cornell University), 60, 3, pp. 1373-1386, 10.1109/tit.2013.2295392, http://arxiv.org/abs/1304.7392.