2
$\begingroup$

While benchmarking a language prototype, I realized that I had a superlinear implementation of a test program, but wasn't sure if it was quadratic or cubic. I stayed up too late and wrote half a page of very messy Python which appears to try some finite-difference method for empirically approximating complexity from the benchmark results.

I'm still trying to reverse-engineer what Past Corbin did, but before I go too much further, can finite-difference methods even do this? I only know formal methods for complexity analysis, and I've never heard of algorithms for doing it automatically other than type systems or other syntactic analysis.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ No, in general there is no way to determine worst-case asymptotic complexity via simulation, just because it is easy to construct algorithms whose asymptotic behavior is not exhibited on any input that is small enough to be tested. This question should probably be migrated to cs.stackexchange.com (and, if this answer doesn't answer your question, maybe clarify the question). $\endgroup$
    – Neal Young
    Sep 13, 2021 at 19:36
  • 1
    $\begingroup$ Concretely, given a Turing Machines $M$ and an input $x$, construct the machine that simulates $M$ on the empty tape either for $f(|x|)$ steps or until completion, whichever comes first, and then returns $\bot$. The running time of this machine is $O(1)$ if $M$ halts on the empty tape and $\Omega(f(n))$ otherwise. $\endgroup$
    – Yonatan N
    Sep 15, 2021 at 5:48
  • $\begingroup$ Can you clarify what you mean by "empirically approximating complexity from the benchmarks"? There seem to be a variety of interpretations of what you could mean, leading to different answers. $\endgroup$
    – Neal Young
    Oct 15, 2021 at 21:10

2 Answers 2

Reset to default
1
$\begingroup$

This is not exactly "finite difference", but when dealing with recurrences, the discrete version of "differential equations" often comes handy.

This video might be very helpful: https://www.youtube.com/watch?v=TWBB-JlmYUc

And perhaps this one too: https://www.youtube.com/watch?v=Kqf0uO0oV6s

Improve this answer
$\endgroup$
1
$\begingroup$

This is exactly the approach taken in certain forms of modern inference of complexity bounds! From Jan Hoffmann's excellent thesis:

In a nutshell, our approach is as follows. We start from an as yet unknown potential function of the form $\sum p_j(n_j)$ with polynomials $p_j$ of a given maximal degree $k$ and $n_j$ referring to the sizes of the parameters. We then derive linear constraints on the coefficients of the $p_j$ by type-checking the program. Recall that the polynomials $p (n)$ of degree $k$ are represented as sums $\sum_{0\leq i\leq k}q_i(n_i)$ with $q_i\geq 0$. Compared with the traditional representation $\Sigma q_i\cdot n^i$, $q_i\geq 0$, the use of binomial coefficients has the following advantages. [...]

  1. it is the largest class $\cal C$ of non-negative, monotone polynomials such that $p\in{\cal C}$ implies $f (n) =p (n +1) −p (n) \in{\cal C}$ (see Chapter 5)

That last point is the crucial "finite difference" connection! It enables doing complexity inference using only linear constraints.

2 obvious drawbacks of this method:

  1. It needs an explicit bound on the polynomial degree, and as such cannot infer exponential time bounds (but who cares?)
  2. It doesn't allow inferring constraints of the form $n\log(n)$. That's more serious.
Improve this answer
$\endgroup$
1
  • $\begingroup$ But OP asks about "empirically approximating complexity from benchmark results", whereas what you describe seems to be about something more sophisticated (analyzing the program via some kind of type checking)... $\endgroup$
    – Neal Young
    Oct 15, 2021 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.