--- res: bibo_abstract: - "We consider the problem of developing automated techniques to aid the average-case complexity analysis of programs. Several classical textbook algorithms have quite efficient average-case complexity, whereas the corresponding worst-case bounds are either inefficient (e.g., QUICK-SORT), or completely ineffective (e.g., COUPONCOLLECTOR). Since the main focus of average-case analysis is to obtain efficient bounds, we consider bounds that are either logarithmic,\r\nlinear, or almost-linear (O(log n), O(n), O(n ยท log n),\r\nrespectively, where n represents the size of the input). Our main contribution is a sound approach for deriving such average-case bounds for randomized recursive programs. Our approach is efficient (a simple linear-time algorithm), and it is based on (a) the analysis of recurrence relations induced by randomized algorithms, and (b) a guess-and-check technique. Our approach can infer the asymptotically optimal average-case bounds for classical randomized algorithms, including RANDOMIZED-SEARCH, QUICKSORT, QUICK-SELECT, COUPON-COLLECTOR, where the worstcase\r\nbounds are either inefficient (such as linear as compared to logarithmic of average-case, or quadratic as compared to linear or almost-linear of average-case), or ineffective. We have implemented our approach, and the experimental results show that we obtain the bounds efficiently for various classical algorithms.@eng" bibo_authorlist: - foaf_Person: foaf_givenName: '1' foaf_name: Anonymous, 1 foaf_surname: Anonymous - foaf_Person: foaf_givenName: '2' foaf_name: Anonymous, 2 foaf_surname: Anonymous - foaf_Person: foaf_givenName: '3' foaf_name: Anonymous, 3 foaf_surname: Anonymous dct_date: 2016^xs_gYear dct_isPartOf: - http://id.crossref.org/issn/2664-1690 dct_language: eng dct_publisher: IST Austria@ dct_title: 'Average-case analysis of programs: Automated recurrence analysis for almost-linear bounds@' ...