Loading [MathJax]/jax/output/HTML-CSS/jax.js

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

  • 1 Department of Electrical and Computer Engineering [Minneapolis]

Let k2 be a fixed integer. Given a bounded sequence of real numbers (an:nk), then for any sequence (fn:n1) of real numbers satisfying the divide-and-conquer recurrence fn=(kmod(n,k))fn/k+mod(n,k)fn/k+an,nk, there is a unique continuous periodic function f:RR with period 1 such that fn=nf(logkn)+o(n). If (an) is periodic with period k,ak=0, and the initial conditions (fi:1ik1) 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)):0x1}. 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)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: divide-and-conquer recurrences,iterated function systems,IFS attractor,self-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]
Funding:
    Source : OpenAIRE Graph
  • Collaborative Research: Information Theory of Data Structures; Funder: National Science Foundation; Code: 0830457

2 Documents citing this article

Consultation statistics

This page has been seen 311 times.
This article's PDF has been downloaded 255 times.