Automated recurrence analysis for almost linear expected runtime bounds
LNCS
Chatterjee, Krishnendu
Fu, Hongfei
Murhekar, Aniket
Majumdar, Rupak
Kunčak, Viktor
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.
Springer
2017
info:eu-repo/semantics/conferenceObject
doc-type:conferenceObject
text
https://research-explorer.app.ist.ac.at/record/628
Chatterjee K, Fu H, Murhekar A. Automated recurrence analysis for almost linear expected runtime bounds. In: Majumdar R, Kunčak V, eds. Vol 10426. Springer; 2017:118-139. doi:<a href="https://doi.org/10.1007/978-3-319-63387-9_6">10.1007/978-3-319-63387-9_6</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-319-63387-9_6
info:eu-repo/semantics/altIdentifier/isbn/978-331963386-2
info:eu-repo/grantAgreement/ICT15-003
info:eu-repo/grantAgreement/FWF/S11407
info:eu-repo/grantAgreement/EC/FP7/279307
info:eu-repo/semantics/openAccess