Abstract: 
We consider the problem of developing automated techniques for solving recurrence relations to aid the expectedruntime analysis of programs. The motivation is that several classical textbook algorithms have quite efficient expectedruntime complexity, whereas the corresponding worstcase bounds are either inefficient (e.g., QuickSort), or completely ineffective (e.g., CouponCollector). Since the main focus of expectedruntime analysis is to obtain efficient bounds, we consider bounds that are either logarithmic, linear or almostlinear (O(log n), O(n), O(n ยท log n), respectively, where n represents the input size). Our main contribution is an efficient (simple lineartime algorithm) sound approach for deriving such expectedruntime bounds for the analysis of recurrence relations induced by randomized algorithms. The experimental results show that our approach can efficiently derive asymptotically optimal expectedruntime bounds for recurrences of classical randomized algorithms, including RandomizedSearch, QuickSort, QuickSelect, CouponCollector, where the worstcase bounds are either inefficient (such as linear as compared to logarithmic expectedruntime complexity, or quadratic as compared to linear or almostlinear expectedruntime complexity), or ineffective.
