uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications
Acad Sinica, Inst Stat Sci, 128,Sec 2,Acad Rd, Taipei 11529, Taiwan..
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
Acad Sinica, Inst Stat Sci, 128,Sec 2,Acad Rd, Taipei 11529, Taiwan..
2017 (English)In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 13, no 4, article id 47Article in journal (Refereed) Published
Abstract [en]

Divide-and-conquer recurrences of the form f (n) = f(left perpendicular n/2 right perpendicular) + f(vertical bar n/2 vertical bar) + g(n) (n >= 2), with g(n) and f(1) given, appear very frequently in the analysis of computer algorithms and related areas. While most previous methods and results focus on simpler crude approximation to the solution, we show that the solution always satisfies the simple identity f(n) = nP(log(2) n) - Q(n) under an optimum (iff) condition on g(n). This form is not only an identity but also an asymptotic expansion because Q(n) is of a smaller order than linearity. Explicit forms for the continuous periodic function P are provided. We show how our results can be easily applied to many dozens of concrete examples collected from the literature and how they can be extended in various directions. Our method of proof is surprisingly simple and elementary but leads to the strongest types of results for all examples to which our theory applies.

Place, publisher, year, edition, pages
ASSOC COMPUTING MACHINERY , 2017. Vol. 13, no 4, article id 47
Keywords [en]
Analysis of algorithms, recurrence relation, asymptotic linearity, periodic oscillation, identity, master theorems, functional equation, asymptotic approximation, uniform continuity, additivity, sensitivity analysis
National Category
Computer Sciences Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-340477DOI: 10.1145/3127585ISI: 000419242000004OAI: oai:DiVA.org:uu-340477DiVA, id: diva2:1178941
Available from: 2018-01-31 Created: 2018-01-31 Last updated: 2018-01-31Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Janson, Svante

Search in DiVA

By author/editor
Janson, Svante
By organisation
Department of Mathematics
In the same journal
ACM Transactions on Algorithms
Computer SciencesMathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 15 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf