[Solved]: What is the running time of this recursive algorithm?

Problem Detail: 

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] 

Asked By : Michael Klein

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51989

3.2K people like this

 Download Related Notes/Documents