DMTCS Proceedings, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)

Font Size:  Small  Medium  Large

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

John C. Kieffer

Abstract


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*:ℝ→ℝ 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]×ℝ 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.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional