Non-polynomial worst-case analysis of recursive programs

K. Chatterjee, H. Fu, A.K. Goharshady, ACM Transactions on Programming Languages and Systems 41 (2019) 20.

Download
No fulltext has been uploaded. References only!

Journal Article | Published | English
Department
Abstract
We study the problem of developing efficient approaches for proving worst-case bounds of non-deterministic recursive programs. Ranking functions are sound and complete for proving termination and worst-case bounds of nonrecursive programs. First, we apply ranking functions to recursion, resulting in measure functions. We show that measure functions provide a sound and complete approach to prove worst-case bounds of non-deterministic recursive programs. Our second contribution is the synthesis of measure functions in nonpolynomial forms. We show that non-polynomial measure functions with logarithm and exponentiation can be synthesized through abstraction of logarithmic or exponentiation terms, Farkas' Lemma, and Handelman's Theorem using linear programming. While previous methods obtain worst-case polynomial bounds, our approach can synthesize bounds of the form $\mathcal{O}(n\log n)$ as well as $\mathcal{O}(n^r)$ where $r$ is not an integer. We present experimental results to demonstrate that our approach can obtain efficiently worst-case bounds of classical recursive algorithms such as (i) Merge-Sort, the divide-and-conquer algorithm for the Closest-Pair problem, where we obtain $\mathcal{O}(n \log n)$ worst-case bound, and (ii) Karatsuba's algorithm for polynomial multiplication and Strassen's algorithm for matrix multiplication, where we obtain $\mathcal{O}(n^r)$ bound such that $r$ is not an integer and close to the best-known bounds for the respective algorithms.
Publishing Year
Date Published
2019-10-01
Journal Title
ACM Transactions on Programming Languages and Systems
Volume
41
Issue
4
Article Number
20
IST-REx-ID

Cite this

Chatterjee K, Fu H, Goharshady AK. Non-polynomial worst-case analysis of recursive programs. ACM Transactions on Programming Languages and Systems. 2019;41(4):20. doi:10.1145/3339984
Chatterjee, K., Fu, H., & Goharshady, A. K. (2019). Non-polynomial worst-case analysis of recursive programs. ACM Transactions on Programming Languages and Systems, 41(4), 20. https://doi.org/10.1145/3339984
Chatterjee, Krishnendu, Hongfei Fu, and Amir Kafshdar Goharshady. “Non-Polynomial Worst-Case Analysis of Recursive Programs.” ACM Transactions on Programming Languages and Systems 41, no. 4 (2019): 20. https://doi.org/10.1145/3339984.
K. Chatterjee, H. Fu, and A. K. Goharshady, “Non-polynomial worst-case analysis of recursive programs,” ACM Transactions on Programming Languages and Systems, vol. 41, no. 4, p. 20, 2019.
Chatterjee K, Fu H, Goharshady AK. 2019. Non-polynomial worst-case analysis of recursive programs. ACM Transactions on Programming Languages and Systems. 41(4), 20.
Chatterjee, Krishnendu, et al. “Non-Polynomial Worst-Case Analysis of Recursive Programs.” ACM Transactions on Programming Languages and Systems, vol. 41, no. 4, ACM, 2019, p. 20, doi:10.1145/3339984.

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1705.00317

Search this title in

Google Scholar