# 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}, 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:

Haskell: [0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0e-2,3.0e-2,9.0e-2,0.34,1.42,11.77,71.68,184.37,1815.91]
C:       [2.0e-6, 1.0e-6, 1.0e-6, 2.0e-6, 1.0e-6, 6.0e-6, 0.00003,0.00027, 0.002209, 0.005127, 0.016665, 0.080549, 0.243611, 0.821537, 4.56265, 24.2044, 272.212]

• I've changed tags and title to make clear that this is an algorithm analysis, not a complexity theory question. "Assuming that multiplication and addition are negligible" -- can you? Really? It's still better to say what you are counting, because chances are you are not counting most things. See also our reference question. – Raphael Jan 18 '16 at 8:04
• 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
• Finally, using fitting methods to derive Landau bounds is probably futile. Any such function can only fit against a fixed set of functions; I'd guess that Mathematica used at worst exponential models there, thus did a bad job capturing super-exponential growth. – Raphael Jan 18 '16 at 8:14
• @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.