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:
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]
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. $\endgroup$ – Raphael♦ Jan 18 '16 at 8:10