A Class of Programs that Admit Exact Complexity Analysis via Newton?s Polynomial Interpolation

• Rafael Sumitani UFMG
• Lucas Silva UFMG
• Frederico Campos UFMG
• Fernando Pereira UFMG

Resumo

We say that a program features the “Single-Complexity Path" (SCP) property if the computational cost of this program can be described by a single equation. Structurally, SCP programs do not have loops controlled by conditional branches. This paper presents a study on the occurrence of single-complexity paths in real-world programs. To this end, we analyze a set of 950 executable C functions obtained from open-source repositories. Out of this lot, 766 functions present a single-complexity path. The paper also demonstrates that the computational cost of many programs with a single-complexity path can be represented by a unique polynomial. We call these programs “Newton Algorithms". We explain how to extract this polynomial for programs whose complexity depends on a single variable. By manually generating inputs for 32 of these 766 C programs, we observe that 23 of them bear this property: their cost model is polynomial on a single variable.

Palavras-chave: Complexity, Interpolation