The Akra-Bazzi theorem and the Master theorem

 Title: The Akra-Bazzi theorem and the Master theorem Author: Manuel Eberl Submission date: 2015-07-14 Abstract: This article contains a formalisation of the Akra-Bazzi method based on a proof by Leighton. It is a generalisation of the well-known Master Theorem for analysing the complexity of Divide & Conquer algorithms. We also include a generalised version of the Master theorem based on the Akra-Bazzi theorem, which is easier to apply than the Akra-Bazzi theorem itself. Some proof methods that facilitate applying the Master theorem are also included. For a more detailed explanation of the formalisation and the proof methods, see the accompanying paper (publication forthcoming). BibTeX: @article{Akra_Bazzi-AFP, author = {Manuel Eberl}, title = {The Akra-Bazzi theorem and the Master theorem}, journal = {Archive of Formal Proofs}, month = jul, year = 2015, note = {\url{http://isa-afp.org/entries/Akra_Bazzi.html}, Formal proof development}, ISSN = {2150-914x}, } License: BSD License Depends on: Landau_Symbols Used by: Closest_Pair_Points Status: [ok] This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.