<p>This is exactly the approach taken in certain forms of modern inference of complexity bounds! From Jan Hoffmann's excellent <a href="https://www.cs.cmu.edu/%7Ejanh/assets/pdf/Hoffmann11.pdf" rel="nofollow noreferrer">thesis</a>:</p>
<blockquote>
<p>In a nutshell, our approach is as follows. We start from an as yet unknown potential function of the form <span class="math-container">$\sum p_j(n_j)$</span> with polynomials <span class="math-container">$p_j$</span> of a given maximal degree <span class="math-container">$k$</span> and <span class="math-container">$n_j$</span> referring to the sizes of the parameters. We then derive linear constraints on the coefficients of the <span class="math-container">$p_j$</span> by type-checking the program. Recall that the polynomials <span class="math-container">$p (n)$</span> of degree <span class="math-container">$k$</span> are represented as sums <span class="math-container">$\sum_{0\leq i\leq k}q_i(n_i)$</span> with <span class="math-container">$q_i\geq 0$</span>. Compared with the
traditional representation <span class="math-container">$\Sigma q_i\cdot n^i$</span>, <span class="math-container">$q_i\geq 0$</span>, the use of binomial coefficients has the
following advantages.
[...]</p>
<ol start="2">
<li>it is the largest class <span class="math-container">$\cal C$</span> of non-negative, monotone polynomials such that <span class="math-container">$p\in{\cal C}$</span> implies <span class="math-container">$f (n) =p (n +1) −p (n) \in{\cal C}$</span> (see Chapter 5)</li>
</ol>
</blockquote>
<p>That last point is the crucial &quot;finite difference&quot; connection! It enables doing complexity inference using only linear constraints.</p>
<p>2 obvious drawbacks of this method:</p>
<ol>
<li>It needs an explicit bound on the polynomial degree, and as such cannot infer exponential time bounds (but who cares?)</li>
<li>It doesn't allow inferring constraints of the form <span class="math-container">$n\log(n)$</span>. That's more serious.</li>
</ol>

CC BY-SA 4.0
2021-10-15T20:19:05.023Z
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)...
Neal Young
CC BY-SA 4.0
2021-10-15T17:47:34.737Z
2021-10-15T17:47:34.737Z
cody
<p>This is not exactly &quot;finite difference&quot;, but when dealing with recurrences, the discrete version of &quot;differential equations&quot; often comes handy.</p>
<p>This video might be very helpful:
<a href="https://www.youtube.com/watch?v=TWBB-JlmYUc" rel="nofollow noreferrer">https://www.youtube.com/watch?v=TWBB-JlmYUc</a></p>
<p>And perhaps this one too:
<a href="https://www.youtube.com/watch?v=Kqf0uO0oV6s" rel="nofollow noreferrer">https://www.youtube.com/watch?v=Kqf0uO0oV6s</a></p>

CC BY-SA 4.0
2021-09-14T04:49:50.210Z
2021-09-14T05:31:13.703Z
2021-09-14T05:31:13.703Z
Avi Tal
<p>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 <a href="https://en.wikipedia.org/wiki/Finite_difference_method" rel="nofollow noreferrer">finite-difference method</a> for empirically approximating complexity from the benchmark results.</p>
<p>I'm still trying to reverse-engineer what Past Corbin did, but before I go too much further, <strong>can finite-difference methods even do this?</strong> 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.</p>

CC BY-SA 4.0
2021-09-13T19:36:12.230Z
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).
Neal Young
CC BY-SA 4.0
2021-09-15T05:48:44.093Z
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.
Yonatan N
CC BY-SA 4.0
2021-10-15T21:10:23.770Z
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.
Neal Young
<na.numerical-analysis>
Can finite difference methods approximate the space/time complexity of given programs?
Corbin
# Can finite difference methods approximate the space/time complexity of given programs?

(Asked by: username_0 on 2021-09-13)

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](https://en.wikipedia.org/wiki/Finite_difference_method) for empirically approximating complexity from the benchmark results.

I'm still trying to reverse-engineer what Past username_0 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.

**Tags:** na.numerical-analysis

> **Comments:**
> **username_1**: 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).  
> **username_2**: 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.  
> **username_1**: 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.  

---

## 2 answers

### Answer by username_3 on 2021-10-15. Score: 1

This is exactly the approach taken in certain forms of modern inference of complexity bounds! From Jan Hoffmann's excellent [thesis](https://www.cs.cmu.edu/%7Ejanh/assets/pdf/Hoffmann11.pdf):

> 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.
> [...]
>
> 2. 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.

> **Comments:**
> **username_1**: 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)...  

---

### Answer by username_4 on 2021-09-14. Score: 1

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>


---

