Tight Worst-Case Bounds for Polynomial Loop Programs
Amir M. Ben-Amram, Geoff W. Hamilton · Lecture notes in computer science · 2019
Abstract In 2008, Ben-Amram, Jones and Kristiansen showed that for a simple programming language—representing non-deterministic imperative programs with bounded loops, and arithmetics limited to addition and multiplication—it is possible to decide precisely whether a program has certain growth-rate properties, in particular whether a computed value, or the program’s running time, has a polynomial growth rate. A natural and intriguing problem was to improve the precision of the information obtained. This paper shows how to obtain asymptotically-tight multivariate polynomial bounds for this class of programs. This is a complete solution: whenever a polynomial bound exists it will be found.