Inferring Complexity Bounds from Recurrence Relations

This is an extended abstract for FSE 23 Student Research Competition. Thisabstract summarizes my research in automated complexity analysis using dynamically inferred recurrence relations with a focus on annihilator method for solving these recurrences. The use of annihilator method allows learning correct bounds for popular classical recursive programs (e.g. 𝑂 (n^2) for quicksort), achieving more precise bounds for exponential programs than previously reported (e.g. 𝑂 ( ( 1+ \sqrt{5} )^n ) for fibonacci), and capturing a wide range of bounds including non-linear polynomial and non-polynomial, logarithmic, and exponential relations. Download paper here