Dynaplex: Analyzing Program Complexity using Dynamically Inferred Recurrence Relations

In this work, we introduce a new dynamic approach for inferring the asymptotic complexity bounds of recursive programs. From program execution traces, we learn recurrence relations 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 linear recurrence relations that represent nontrivial, potentially nonlinear polynomial and non-polynomial, complexity bounds such as O(n^{1.58}) for Karatsuba multiplication algorithm. Download paper here