Automated Recurrence Analysis for Almost-Linear Expected-Runtime Bounds

Krishnendu Chatterjee, Hongfei Fu, Aniket Murhekar

We consider the problem of developing automated techniques for solving recurrence relations to aid the expected-runtime analysis of programs. Several classical textbook algorithms…