Inferring Complexity Bounds from Recurrence Relations

Abstract

Determining program complexity bounds is a fundamental problem with a variety of applications in software development. In this paper we present a novel approach for computing the asymptotic complexity bounds of non-deterministic recursive programs by solving dynamically inferred recurrence relations. Recurrences are inferred from program execution traces and solved using the annihilator method and Master Theorem to obtain closed-form solutions representing the complexity bounds.

BibTeX

@inproceedings{Ishimwe:FSE23,
  author    = {Didier Ishimwe},
  title     = {Inferring Complexity Bounds from Recurrence Relations},
  booktitle = {{ESEC/SIGSOFT} {FSE}},
  pages     = {2198--2200},
  publisher = {{ACM}},
  year      = {2023},
}

Inferring Complexity Bounds from Recurrence Relations

Abstract

Related papers