[{"type":"technical_report","pubrep_id":"619","status":"public","_id":"5447","file_date_updated":"2020-07-14T12:46:58Z","date_updated":"2020-07-14T23:05:06Z","ddc":[],"creator":{"login":"dernst","id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},"alternative_title":[],"month":"07","abstract":[{"lang":"eng"}],"oa_version":"Published Version","publication_status":"published","publication_identifier":{"issn":[]},"language":[{}],"file":[{"access_level":"closed","relation":"main_file","content_type":"text/plain","file_id":"6406","checksum":"cf53cdb6d092e68db0b4a0a1506ef8fb","creator":"dernst","date_updated":"2020-07-14T12:46:58Z","file_size":281,"date_created":"2019-05-10T13:32:16Z","file_name":"listofauthors.txt"},{"content_type":"application/pdf","access_level":"open_access","relation":"main_file","file_id":"6407","checksum":"7bdd94ba13aa0dec9c46887fcf13870b","date_updated":"2020-07-14T12:46:58Z","file_size":563642,"creator":"dernst","date_created":"2019-05-10T13:32:16Z","file_name":"popl2017b.pdf"}],"author":[{"first_name":"1","last_name":"Anonymous"},{"last_name":"Anonymous","first_name":"2"},{"last_name":"Anonymous","first_name":"3"}],"dini_type":"doc-type:other","citation":{"ista":"Anonymous 1, Anonymous 2, Anonymous 3. 2016. Average-case analysis of programs: Automated recurrence analysis for almost-linear bounds, IST Austria, 20p.","chicago":"Anonymous, 1, 2 Anonymous, and 3 Anonymous. Average-Case Analysis of Programs: Automated Recurrence Analysis for Almost-Linear Bounds. IST Austria, 2016.","apa":"Anonymous, 1, Anonymous, 2, & Anonymous, 3. (2016). Average-case analysis of programs: Automated recurrence analysis for almost-linear bounds. IST Austria.","ieee":"1 Anonymous, 2 Anonymous, and 3 Anonymous, Average-case analysis of programs: Automated recurrence analysis for almost-linear bounds. IST Austria, 2016.","short":"1 Anonymous, 2 Anonymous, 3 Anonymous, Average-Case Analysis of Programs: Automated Recurrence Analysis for Almost-Linear Bounds, IST Austria, 2016.","mla":"Anonymous, 1, et al. Average-Case Analysis of Programs: Automated Recurrence Analysis for Almost-Linear Bounds. IST Austria, 2016."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"uri_base":"https://research-explorer.ista.ac.at","page":"20","date_created":"2018-12-12T11:39:23Z","date_published":"2016-07-15T00:00:00Z","has_accepted_license":"1","dc":{"description":["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."],"identifier":["https://research-explorer.ista.ac.at/record/5447","https://research-explorer.ista.ac.at/download/5447/6407"],"source":["Anonymous 1, Anonymous 2, Anonymous 3. Average-Case Analysis of Programs: Automated Recurrence Analysis for Almost-Linear Bounds. IST Austria; 2016."],"relation":["info:eu-repo/semantics/altIdentifier/issn/2664-1690"],"publisher":["IST Austria"],"type":["info:eu-repo/semantics/other","doc-type:other","text","http://purl.org/coar/resource_type/c_1843"],"date":["2016"],"subject":["ddc:000"],"language":["eng"],"rights":["info:eu-repo/semantics/openAccess"],"creator":["Anonymous, 1","Anonymous, 2","Anonymous, 3"],"title":["Average-case analysis of programs: Automated recurrence analysis for almost-linear bounds","IST Austria Technical Report"]},"day":"15"}]