Average-Case Analysis of Programs: Automated Recurrence Analysis for Almost-Linear Bounds

Anonymous, 1 and Anonymous, 2 and Anonymous, 3 (2016) Average-Case Analysis of Programs: Automated Recurrence Analysis for Almost-Linear Bounds. Technical Report. Anonymous. (Submitted)

[img] Text
popl2017b.pdf - Submitted Version
Restricted to Registered users only
Available under License All rights reserved.
[IST-2016-619-v1+1]
Download (420Kb)
[img] Text
listofauthors2.txt - Additional Metadata
Restricted to Repository staff only
[IST-2016-619-v1+2]
Download (281b)

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.

Item Type: Monograph (Technical Report)
Subjects: 000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 005 Computer programming, programs & data
000 Computer science, knowledge & general works > 000 Computer science, knowledge & systems > 006 Special computer methods
Depositing User: Anonymous User
Date Deposited: 15 Jul 2016 09:04
Last Modified: 15 Jul 2019 14:47
URI: https://repository.ist.ac.at/id/eprint/619

Actions (login required)

View Item View Item