# Average-case analysis of programs: Automated recurrence analysis for almost-linear bounds

Anonymous 1, Anonymous 2, Anonymous 3. 2016. Average-case analysis of programs: Automated recurrence analysis for almost-linear bounds, IST Austria, 20p.

Download

*Technical Report*|

*Published*|

*English*

Author

Anonymous, 1;
Anonymous, 2;
Anonymous, 3

Series Title

IST Austria Technical Report

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,
linear, or almost-linear (O(log n), O(n), O(n · log n),
respectively, 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
bounds 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.

Publishing Year

Date Published

2016-07-15

Page

20

ISSN

IST-REx-ID

### Cite this

Anonymous 1, Anonymous 2, Anonymous 3.

*Average-Case Analysis of Programs: Automated Recurrence Analysis for Almost-Linear Bounds*. IST Austria; 2016.Anonymous, 1, Anonymous, 2, & Anonymous, 3. (2016).

*Average-case analysis of programs: Automated recurrence analysis for almost-linear bounds*. IST Austria.Anonymous, 1, 2 Anonymous, and 3 Anonymous.

*Average-Case Analysis of Programs: Automated Recurrence Analysis for Almost-Linear Bounds*. IST Austria, 2016.1 Anonymous, 2 Anonymous, and 3 Anonymous,

*Average-case analysis of programs: Automated recurrence analysis for almost-linear bounds*. IST Austria, 2016.Anonymous, 1, et al.

*Average-Case Analysis of Programs: Automated Recurrence Analysis for Almost-Linear Bounds*. IST Austria, 2016.**All files available under the following license(s):**

**Copyright Statement:**

**This Item is protected by copyright and/or related rights.**[...]

**Main File(s)**

File Name

**listofauthors.txt**281 bytes

Access Level

Closed Access

Date Uploaded

2019-05-10

MD5 Checksum

cf53cdb6d092e68db0b4a0a1506ef8fb

File Name

popl2017b.pdf
563.64 KB

Access Level

Open Access

Date Uploaded

2019-05-10

MD5 Checksum

7bdd94ba13aa0dec9c46887fcf13870b