Tight Worst-Case Bounds for Polynomial Loop Programs

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