Automated recurrence analysis for almost linear expected runtime bounds Conference Paper

Author(s): Chatterjee, Krishnendu; Fu, Hongfei; Murhekar, Aniket
Title: Automated recurrence analysis for almost linear expected runtime bounds
Title Series: LNCS
Affiliation IST Austria
Abstract: 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.
Conference Title: CAV: Computer Aided Verification
Volume: 10426
Conference Dates: July 24 - 28, 2017
Conference Location: Heidelberg, Germany
Publisher: Springer  
Date Published: 2017-01-01
Start Page: 118
End Page: 139
Sponsor: The research is partially supported by Vienna Science and Technology Fund (WWTF) ICT15-003, Austrian Science Fund (FWF) NFN Grant No. S11407-N23 (RiSE/SHiNE), ERC Start grant (279307: Graph Games), the Natural Science Foundation of China (NSFC) under Gran
DOI: 10.1007/978-3-319-63387-9_6
Notes: We thank all reviewers for valuable comments.
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work