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

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

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-

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.

StackExchange Computer Science Q#51989, answer score: 3