Alternating runtime and size complexity analysis of integer programs

Abstract. We present a modular approach to automatic complexity analysis. Based on a novel alternation between finding symbolic time bounds for program parts and using these to infer size bounds on pro-gram variables, we can restrict each analysis step to a small part of the program while maintaining a high level of precision. Extensive experi-ments with the implementation of our method demonstrate its perfor-mance and power in comparison with other tools.