{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T18:51:19Z","timestamp":1777488679269,"version":"3.51.4"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T00:00:00Z","timestamp":1634256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-19-1-0054"],"award-info":[{"award-number":["W911NF-19-1-0054"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1948536, 2107035"],"award-info":[{"award-number":["1948536, 2107035"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2021,10,20]]},"abstract":"<jats:p>\n            Being able to detect program runtime complexity is useful in many tasks (e.g., checking expected performance and identifying potential security vulnerabilities). In this work, we introduce a new dynamic approach for inferring the asymptotic complexity bounds of recursive programs. From program execution traces, we learn\n            <jats:italic>recurrence relations<\/jats:italic>\n            and solve them using pattern matching to obtain closed-form solutions representing the complexity bounds of the program. This approach allows us to efficiently infer simple recurrence relations that represent nontrivial, potentially nonlinear polynomial and non-polynomial, complexity bounds.\n          <\/jats:p>\n          <jats:p>\n            We present Dynaplex, a tool that implements these ideas to automatically generate recurrence relations from execution traces. Our preliminary results on popular and challenging recursive programs show that Dynaplex can learn precise relations capturing worst-case complexity bounds (e.g.,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) for mergesort,\n            <jats:italic>O<\/jats:italic>\n            (2\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            ) for Tower of Hanoi and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1.58<\/jats:sup>\n            ) for Karatsuba\u2019s multiplication algorithm).\n          <\/jats:p>","DOI":"10.1145\/3485515","type":"journal-article","created":{"date-parts":[[2021,10,15]],"date-time":"2021-10-15T19:18:28Z","timestamp":1634325508000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Dynaplex: analyzing program complexity using dynamically inferred recurrence relations"],"prefix":"10.1145","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8470-3835","authenticated-orcid":false,"given":"Didier","family":"Ishimwe","sequence":"first","affiliation":[{"name":"University of Nebraska-Lincoln, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6599-2528","authenticated-orcid":false,"given":"KimHao","family":"Nguyen","sequence":"additional","affiliation":[{"name":"University of Nebraska-Lincoln, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4255-4592","authenticated-orcid":false,"given":"ThanhVu","family":"Nguyen","sequence":"additional","affiliation":[{"name":"George Mason University, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,10,15]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2009.12.008"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69166-2_15"},{"key":"e_1_2_2_3_1","volume-title":"Cost Analysis of Java Bytecode. In European Symposium on Programming. 157\u2013172","author":"Albert Elvira","year":"2007"},{"key":"e_1_2_2_4_1","volume-title":"Rajamani","author":"Ball Thomas","year":"2001"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3386035"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2866575"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2009.5070545"},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3339984","article-title":"Non-polynomial worst-case analysis of recursive programs","volume":"41","author":"Chatterjee Krishnendu","year":"2019","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"e_1_2_2_9_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3408979"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/543552.512538"},{"key":"e_1_2_2_12_1","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"Moura Leonardo De"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46520-3_30"},{"key":"e_1_2_2_14_1","unstructured":"Paul J Drongowski. 2007. Instruction-based sampling: A new performance analysis technique for AMD family 10h processors. Advanced Micro Devices.  Paul J Drongowski. 2007. Instruction-based sampling: A new performance analysis technique for AMD family 10h processors. Advanced Micro Devices."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293880.3294090"},{"key":"e_1_2_2_16_1","unstructured":"Jeff Erickson. 2013. Solving Recurrences. http:\/\/jeffe.cs.illinois.edu\/teaching\/algorithms\/notes\/99-recurrences.pdf  Jeff Erickson. 2013. Solving Recurrences. http:\/\/jeffe.cs.illinois.edu\/teaching\/algorithms\/notes\/99-recurrences.pdf"},{"key":"e_1_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Michael D. Ernst Jeff H. Perkins Philip J. Guo Stephen McCamant Carlos Pacheco Matthew S. Tschantz and Chen Xiao. 2007. The Daikon system for dynamic detection of likely invariants. Science of Computer Programming 35\u201345.  Michael D. Ernst Jeff H. Perkins Philip J. Guo Stephen McCamant Carlos Pacheco Matthew S. Tschantz and Chen Xiao. 2007. The Daikon system for dynamic detection of likely invariants. Science of Computer Programming 35\u201345.","DOI":"10.1016\/j.scico.2007.01.015"},{"key":"e_1_2_2_19_1","doi-asserted-by":"crossref","unstructured":"Azadeh Farzan and Zachary Kincaid. 2015. Compositional recurrence analysis. In 2015 Formal Methods in Computer-Aided Design (FMCAD). 57\u201364.  Azadeh Farzan and Zachary Kincaid. 2015. Compositional recurrence analysis. In 2015 Formal Methods in Computer-Aided Design (FMCAD). 57\u201364.","DOI":"10.1109\/FMCAD.2015.7542253"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90145-R"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1287624.1287681"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/872726.806987"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/507669.507666"},{"key":"e_1_2_2_24_1","volume-title":"An inherently iterative computation of Ackermann\u2019s function. Theoretical computer science, 57, 2-3","author":"Grossman Jerrold W","year":"1988"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70545-1_35"},{"key":"e_1_2_2_26_1","volume-title":"SPEED: Symbolic Complexity Bound Analysis. In Computer Aided Verification","author":"Gulwani Sumit","year":"2009"},{"key":"e_1_2_2_27_1","doi-asserted-by":"crossref","unstructured":"Sumit Gulwani Sagar Jain and Eric Koskinen. 2009. Control-flow Refinement and Progress Invariants for Bound Analysis. In Programming Language Design and Implementation. 375\u2013385.  Sumit Gulwani Sagar Jain and Eric Koskinen. 2009. Control-flow Refinement and Progress Invariants for Bound Analysis. In Programming Language Design and Implementation. 375\u2013385.","DOI":"10.1145\/1543135.1542518"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1594834.1480898"},{"key":"e_1_2_2_29_1","volume-title":"Chilimbi","author":"Gulwani Sumit","year":"2009"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-020-2649-2"},{"key":"e_1_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Thomas A. Henzinger Ranjit Jhala Rupak Majumdar and Gregoire Sutre. 2002. Lazy Abstraction. In Principles of Programming Languages. ACM 58\u201370.  Thomas A. Henzinger Ranjit Jhala Rupak Majumdar and Gregoire Sutre. 2002. Lazy Abstraction. In Principles of Programming Languages. ACM 58\u201370.","DOI":"10.1145\/565816.503279"},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Jan Hoffmann Klaus Aehlig and Martin Hofmann. 2011. Multivariate amortized resource analysis. In Principles of Programming Languages. 357\u2013370.  Jan Hoffmann Klaus Aehlig and Martin Hofmann. 2011. Multivariate amortized resource analysis. In Principles of Programming Languages. 357\u2013370.","DOI":"10.1145\/1925844.1926427"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11957-6_16"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/640128.604148"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.5421762"},{"key":"e_1_2_2_36_1","unstructured":"Anirudh Jayaraman. 2015. Karatsuba Multiplication Algorithm - Python Code. https:\/\/pythonandr.com\/2015\/10\/13\/karatsuba-multiplication-algorithm-python-code\/  Anirudh Jayaraman. 2015. Karatsuba Multiplication Algorithm - Python Code. https:\/\/pythonandr.com\/2015\/10\/13\/karatsuba-multiplication-algorithm-python-code\/"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3140587.3062373"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290368"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3428257"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314634"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3213846.3213874"},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Xavier Leroy. 2006. Formal certification of a compiler back-end or: programming a compiler with a proof assistant. In Principles of Programming Languages. ACM 42\u201354.  Xavier Leroy. 2006. Formal certification of a compiler back-end or: programming a compiler with a proof assistant. In Principles of Programming Languages. ACM 42\u201354.","DOI":"10.1145\/1111320.1111042"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)81042-9"},{"key":"e_1_2_2_44_1","doi-asserted-by":"crossref","unstructured":"ThanhVu Nguyen Timos Antonopoulos Andrew Ruef and Michael Hicks. 2017. A Counterexample-guided Approach to Finding Numerical Invariants. In Foundations of Software Engineering. ACM 605\u2013615.  ThanhVu Nguyen Timos Antonopoulos Andrew Ruef and Michael Hicks. 2017. A Counterexample-guided Approach to Finding Numerical Invariants. In Foundations of Software Engineering. ACM 605\u2013615.","DOI":"10.1145\/3106237.3106281"},{"key":"e_1_2_2_45_1","volume-title":"Automated Software Engineering","author":"Nguyen ThanhVu"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3416507.3423189"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE.2012.6227149"},{"key":"e_1_2_2_48_1","unstructured":"Ocaml.org. 2021. 99 Problems in OCaml. https:\/\/ocaml.org\/learn\/tutorials\/99problems.html  Ocaml.org. 2021. 99 Problems in OCaml. https:\/\/ocaml.org\/learn\/tutorials\/99problems.html"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3134073"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_50"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-016-9402-4"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2714064.2660234"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3093333.3009864"},{"key":"e_1_2_2_54_1","unstructured":"Termination Competitions. 2021. Complexity Benchmarks. https:\/\/termcomp.github.io\/  Termination Competitions. 2021. Complexity Benchmarks. https:\/\/termcomp.github.io\/"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3290326"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133903"},{"key":"e_1_2_2_57_1","unstructured":"Jianan Yao Gabriel Ryan Justin Wong Suman Jana and Ronghui Gu. 2020. Learning nonlinear loop invariants with gated continuous logic networks. In Programming Language Design and Implementation. ACM 106\u2013120.  Jianan Yao Gabriel Ryan Justin Wong Suman Jana and Ronghui Gu. 2020. Learning nonlinear loop invariants with gated continuous logic networks. In Programming Language Design and Implementation. ACM 106\u2013120."},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254064.2254074"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485515","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485515","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485515","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:40Z","timestamp":1750191520000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485515"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,15]]},"references-count":57,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2021,10,20]]}},"alternative-id":["10.1145\/3485515"],"URL":"https:\/\/doi.org\/10.1145\/3485515","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,15]]},"assertion":[{"value":"2021-10-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}