Tight Polynomial Bounds for Loop Programs in Polynomial Space

A. M. Ben-Amram, G. W. Hamilton

We consider the following problem: given a program, find tight asymptotic bounds on the values of some variables at the end of the computation (or at any given program point) in te…