10.1007/978-3-319-63387-9_6
Chatterjee, Krishnendu
Krishnendu
Chatterjee0000-0002-4561-241X
Fu, Hongfei
Hongfei
Fu
Murhekar, Aniket
Aniket
Murhekar
Automated recurrence analysis for almost linear expected runtime bounds
LNCS
Springer
2017
2018-12-11T11:47:35Z
2020-01-21T13:21:18Z
conference
https://research-explorer.app.ist.ac.at/record/628
https://research-explorer.app.ist.ac.at/record/628.json
978-331963386-2
We consider the problem of developing automated techniques for solving recurrence relations to aid the expected-runtime analysis of programs. The motivation is that several classical textbook algorithms have quite efficient expected-runtime complexity, whereas the corresponding worst-case bounds are either inefficient (e.g., Quick-Sort), or completely ineffective (e.g., Coupon-Collector). Since the main focus of expected-runtime analysis is to obtain efficient bounds, we consider bounds that are either logarithmic, linear or almost-linear (O(log n), O(n), O(n ยท log n), respectively, where n represents the input size). Our main contribution is an efficient (simple linear-time algorithm) sound approach for deriving such expected-runtime bounds for the analysis of recurrence relations induced by randomized algorithms. The experimental results show that our approach can efficiently derive asymptotically optimal expected-runtime bounds for recurrences of classical randomized algorithms, including Randomized-Search, Quick-Sort, Quick-Select, Coupon-Collector, where the worst-case bounds are either inefficient (such as linear as compared to logarithmic expected-runtime complexity, or quadratic as compared to linear or almost-linear expected-runtime complexity), or ineffective.