# What is the running time of this recursive algorithm?

I made the following (ungolfed) Haskell program for the code golf challenge of computing the first $n$ values of A229037.

This is my proposed solution to compute the $n$th value:

a n | n<1        = 0
| n<3        = 1
| otherwise  = head (goods n)

goods n = [x | x <- [1..], isGood x n]

isGood x n = and [ x - a(n-k) /= a(n-k) - a(n-k-k) || a(n-k-k) == 0 | k <- [1..n] ]

Note that Haskell does not automatically cache or memoize these values.

The OEIS page for the sequence gives the fact that $a(n) \leq (n+1)/2$, so the [1..] could be replaced by [1..(n+1)/2], as the algorithm will never reach an $x$ greater than $\frac{n+1}{2}$.

Attempting to count function calls, I derived the following upper bound $T(n)$, the number of function calls that the algorithm takes for an input $n$:

\begin{align} T(n) &= \sum_{x=1}^{(n+1)/{2}} \sum_{k=1}^{n} 2~T(n-k) + 2~T(n-2 k) \\ &\leq \sum_{x=1}^{(n+1)/{2}} \sum_{k=1}^{n} ~T(n-k)\\ &\leq \sum_{x=1}^{(n+1)/{2}} \sum_{k=1}^{n} 4~T(n-1)\\ &\leq \sum_{x=1}^{(n+1)/{2}} 4~n~T(n-1)\\ &\leq 4~n~T(n-1)~\frac{n+1}{2}\\ &\leq 2~n~(n+1)~T(n-1) ) \end{align}

I plugged the final formula into Mathematica:

RSolve[{T[n] == 2*T[n - 1]*n*(n + 1), T[1] == 1}, T[n], n]

And got, after a little simplification: $T(n) \leq ~2^n~n!~(n + 1)!$

The average ratio between this and the Haskell program execution time, for $n \in [12,20]$ is $2.0 \cdot 10^{39}$ and the standard deviation of the ratios is around $6.0 \cdot 10^{39}$. (Curiously enough, the log plot of the ratios appears to be a straight line).

The ratios with the first line, defining $T(n)$, have a mean and standard deviation of $4.8 \cdot 10^6$ and $1.8 \cdot 10^6$, respectively, but its plot jumps around a lot.

How can I get a better bound on the time complexity of this algorithm?

Here is the algorithm in valid C (minus forward declarations), which I believe is roughly equivalent to the Haskell code:

int a(int n){
if (n < 1) {
return 0;
} else if (n < 3) {
return 1;
} else {
return lowestValid(n);
}
}

int lowestValid(int n){
int possible = 1; // Without checking, we know that this will not exceed (n+1)/2

while (notGood(possible, n)) {
possible++;
}
return possible;
}

int notGood(int possible, int n){
int k = 1;

while (k <= n) {
if ( ((possible - a(n-k)) == (a(n-k) - a(n-2*k))) && (a(n-2*k) != 0) ) {
return 1;
} else {
k++;
}
}
return 0;
}

The C version takes about 5 minutes to compute $a(17)$ and the Haskell version takes about the same for $a(19)$.

The first times of the versions:

• Have you tried plotting your result (with some constant factor) against actual measure running times? (It's often more informative to plot the ratio and guess if it converges to something in $O(1)$.) That said, I find it hard to help here since the ansatz for $T$ depends on the particulars of Haskell, which not everyone here speaks. Specifically, how is this set comprehension evaluated? Is a being memoized? You may get better answers (or any, really!) if you included a pseudo-code version that exposes as much of what actually happens as necessary for a rigorous analysis. – Raphael Jan 18 '16 at 8:10
• @Raphael Your comments were very helpful. I'll look into it more when I have some time. Also, the $O(n^22)$ came from fitting the logarithms of the values to a line, which was more a shot in the dark than anything else. – Michael Klein Jan 18 '16 at 9:37
You can write your recurrence as $$T(n) = (n+1)(T(n-1) + 2T(n-2) + T(n-3) + 2T(n-4) + \cdots).$$ In particular, $T(n) \geq (n+1) T(n-1)$. This means that the sequence $T(n)$ grows very rapidly, and in particular $$T(n-1) + 2T(n-2) + \cdots \leq T(n-1) \left[ 1 + \frac{2}{n} + \frac{1}{n(n-1)} + \frac{2}{n(n-1)(n-2)} + \cdots \right] = (1+O(1/n)) T(n-1).$$ Therefore $$T(n) \leq (n+O(1)) T(n-1).$$ This means that $$T(n) = O((n+O(1))!),$$ and so $$T(n) = O\left(n^{O(1)} (n/e)^n\right).$$ This improves on your bound by a square root.