---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Hongfei
foaf_name: Fu, Hongfei
foaf_surname: Fu
- foaf_Person:
foaf_givenName: Aniket
foaf_name: Murhekar, Aniket
foaf_surname: Murhekar
bibo_doi: 10.1007/978-3-319-63387-9_6
bibo_volume: 10426
dct_date: 2017^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/978-331963386-2
dct_language: eng
dct_publisher: Springer@
dct_title: Automated recurrence analysis for almost linear expected runtime bounds@
...