conference paper
Automated recurrence analysis for almost linear expected runtime bounds
LNCS
published
yes
Krishnendu
Chatterjee
author 2E5DCA20-F248-11E8-B48F-1D18A9856A870000-0002-4561-241X
Hongfei
Fu
author
Aniket
Murhekar
author
RupakMajumdar
editor
ViktorKunčak
editor
KrCh
department
CAV: Computer Aided Verification
Efficient Algorithms for Computer Aided Verification
project
Game Theory
project
Quantitative Graph Games: Theory and Applications
project
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.
Springer2017Heidelberg, Germany
eng
978-331963386-210.1007/978-3-319-63387-9_6
10426118 - 139
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>
K. Chatterjee, H. Fu, and A. Murhekar, “Automated recurrence analysis for almost linear expected runtime bounds,” presented at the CAV: Computer Aided Verification, Heidelberg, Germany, 2017, vol. 10426, pp. 118–139.
Chatterjee, Krishnendu, et al. <i>Automated Recurrence Analysis for Almost Linear Expected Runtime Bounds</i>. Edited by Rupak Majumdar and Viktor Kunčak, vol. 10426, Springer, 2017, pp. 118–39, doi:<a href="https://doi.org/10.1007/978-3-319-63387-9_6">10.1007/978-3-319-63387-9_6</a>.
K. Chatterjee, H. Fu, A. Murhekar, in:, R. Majumdar, V. Kunčak (Eds.), Springer, 2017, pp. 118–139.
Chatterjee, K., Fu, H., & Murhekar, A. (2017). Automated recurrence analysis for almost linear expected runtime bounds. In R. Majumdar & V. Kunčak (Eds.) (Vol. 10426, pp. 118–139). Presented at the CAV: Computer Aided Verification, Heidelberg, Germany: Springer. <a href="https://doi.org/10.1007/978-3-319-63387-9_6">https://doi.org/10.1007/978-3-319-63387-9_6</a>
Chatterjee, Krishnendu, Hongfei Fu, and Aniket Murhekar. “Automated Recurrence Analysis for Almost Linear Expected Runtime Bounds.” edited by Rupak Majumdar and Viktor Kunčak, 10426:118–39. Springer, 2017. <a href="https://doi.org/10.1007/978-3-319-63387-9_6">https://doi.org/10.1007/978-3-319-63387-9_6</a>.
Chatterjee K, Fu H, Murhekar A. 2017. Automated recurrence analysis for almost linear expected runtime bounds. CAV: Computer Aided Verification, LNCS, vol. 10426. 118–139.
6282018-12-11T11:47:35Z2020-01-16T12:37:59Z