---
_id: '7014'
abstract:
- lang: eng
  text: "We study the problem of developing efficient approaches for proving\r\nworst-case
    bounds of non-deterministic recursive programs. Ranking functions\r\nare sound
    and complete for proving termination and worst-case bounds of\r\nnonrecursive
    programs. First, we apply ranking functions to recursion,\r\nresulting in measure
    functions. We show that measure functions provide a sound\r\nand complete approach
    to prove worst-case bounds of non-deterministic recursive\r\nprograms. Our second
    contribution is the synthesis of measure functions in\r\nnonpolynomial forms.
    We show that non-polynomial measure functions with\r\nlogarithm and exponentiation
    can be synthesized through abstraction of\r\nlogarithmic or exponentiation terms,
    Farkas' Lemma, and Handelman's Theorem\r\nusing linear programming. While previous
    methods obtain worst-case polynomial\r\nbounds, our approach can synthesize bounds
    of the form $\\mathcal{O}(n\\log n)$\r\nas well as $\\mathcal{O}(n^r)$ where $r$
    is not an integer. We present\r\nexperimental results to demonstrate that our
    approach can obtain efficiently\r\nworst-case bounds of classical recursive algorithms
    such as (i) Merge-Sort, the\r\ndivide-and-conquer algorithm for the Closest-Pair
    problem, where we obtain\r\n$\\mathcal{O}(n \\log n)$ worst-case bound, and (ii)
    Karatsuba's algorithm for\r\npolynomial multiplication and Strassen's algorithm
    for matrix multiplication,\r\nwhere we obtain $\\mathcal{O}(n^r)$ bound such that
    $r$ is not an integer and\r\nclose to the best-known bounds for the respective
    algorithms."
article_number: '20'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Hongfei
  full_name: Fu, Hongfei
  last_name: Fu
- first_name: Amir Kafshdar
  full_name: Goharshady, Amir Kafshdar
  id: 391365CE-F248-11E8-B48F-1D18A9856A87
  last_name: Goharshady
  orcid: 0000-0003-1702-6584
citation:
  ama: Chatterjee K, Fu H, Goharshady AK. Non-polynomial worst-case analysis of recursive
    programs. <i>ACM Transactions on Programming Languages and Systems</i>. 2019;41(4).
    doi:<a href="https://doi.org/10.1145/3339984">10.1145/3339984</a>
  apa: Chatterjee, K., Fu, H., &#38; Goharshady, A. K. (2019). Non-polynomial worst-case
    analysis of recursive programs. <i>ACM Transactions on Programming Languages and
    Systems</i>. ACM. <a href="https://doi.org/10.1145/3339984">https://doi.org/10.1145/3339984</a>
  chicago: Chatterjee, Krishnendu, Hongfei Fu, and Amir Kafshdar Goharshady. “Non-Polynomial
    Worst-Case Analysis of Recursive Programs.” <i>ACM Transactions on Programming
    Languages and Systems</i>. ACM, 2019. <a href="https://doi.org/10.1145/3339984">https://doi.org/10.1145/3339984</a>.
  ieee: K. Chatterjee, H. Fu, and A. K. Goharshady, “Non-polynomial worst-case analysis
    of recursive programs,” <i>ACM Transactions on Programming Languages and Systems</i>,
    vol. 41, no. 4. ACM, 2019.
  ista: 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.
  mla: Chatterjee, Krishnendu, et al. “Non-Polynomial Worst-Case Analysis of Recursive
    Programs.” <i>ACM Transactions on Programming Languages and Systems</i>, vol.
    41, no. 4, 20, ACM, 2019, doi:<a href="https://doi.org/10.1145/3339984">10.1145/3339984</a>.
  short: K. Chatterjee, H. Fu, A.K. Goharshady, ACM Transactions on Programming Languages
    and Systems 41 (2019).
date_created: 2019-11-13T08:33:43Z
date_published: 2019-10-01T00:00:00Z
date_updated: 2026-09-15T22:31:02Z
day: '01'
department:
- _id: KrCh
doi: 10.1145/3339984
ec_funded: 1
external_id:
  arxiv:
  - '1705.00317'
  isi:
  - '000564108400001'
fulldoi: https://doi.org/10.1145/3339984
intvolume: '        41'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1705.00317
month: '10'
oa: 1
oa_version: Preprint
project:
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 267066CE-B435-11E9-9278-68D0E5697425
  name: Quantitative Analysis of Probabilistic Systems with a focus on Crypto-Currencies
- _id: 266EEEC0-B435-11E9-9278-68D0E5697425
  name: Quantitative Game-theoretic Analysis of Blockchain Applications and Smart
    Contracts
publication: ACM Transactions on Programming Languages and Systems
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
  record:
  - id: '639'
    relation: earlier_version
    status: public
  - id: '8934'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Non-polynomial worst-case analysis of recursive programs
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 41
year: '2019'
...