Example for the analysis of a recursive function

Question

l is a matrix of size [1...n, 1...n]
function: rec(i,j)
 if (i*j == 0)
 return 1
 else
 if (l[i,j] == 0)
 l[i,j] = 1 * rec(i-1,j) + 2 * rec(i,j-1) + 3 * rec(i-1,j-1)
 return l[i,j]
end_function
for i=1 to n
 for j=1 to n
 l[i,j] = 0
rec(n,n)

The nested for's are O(n²). But i have difficulties to analyse the recursive part. There is another variation of this example with l as 3d. And the essential part of 3drec function is defined as:

if (l[i,j,k] == 0)
 l[i,j,k] = 2 * rec(i-1,j,k) + 2 * rec(i,j-1,k) + 2 * rec(i,j,k-1)

Anyway let's think about the 2d version again. I thought something like that (that's the running time for the whole code including the nested loops):

T(n) = T(n-1, n²) + T(n, n-1²) + T(n-1², n-1²)

And i'm stuck here. Besides i don't know if i did right till this point.

• mrk: $T$ is a function of one variable (or two). Make up your mind and you need a base case for your recursion to be defined properly.
• A.B.: base case is not the problem, it's T(1). if i could solve the rest of the problem, i wouldn't post it here. i just need the solution till a proper recurrence. Then I could solve the rest of the recurrence equality.
• Peter Shor: Do you want the time bounds with or without memoization?
• vonbrand: @PeterShor, I understand the question as analyzing exactly the algorithm as written. Perhaps we could come up with a faster way to compute $l[i, j],ドル but that would be cheating...

Answer 1

The running time is exponential. As Yuval showed in his answer, we have

$$f(i,j) = \begin{cases} O(1), & i = 0 \text{ or } j = 0, \\ f(i-1,j) + f(i,j-1) + f(i-1,j-1) + O(1), & \text{otherwise}. \end{cases}$$

Let's look at a $g = O(f)$ defined by $g(i,0)=g(0,i)=1$ and $g(i,j)= g(i,j-1) + g(i-1,j)$.

This gives the array $$ \begin{array}{ccccc} 1&1&1&1&1\cr 1&2&3&4&5\cr 1&3&6&10&15\cr 1&4&10&20&35\1円&5&15&35&70 \end{array}$$ which you should recognize as binomial coefficients. The term $g(i,i) = {2i \choose i},$ which grows as $\Theta(\frac{1}{i^{1/2}}4^i)$. This shows that the growth of $f$ is exponential.

The easiest way I know to find the exact growth formula is to compute the first few terms of the sequence and look it up on the Online Encyclopedia of Integer Sequences. Using 1 for all the $O(1)$ terms, computing them using a spreadsheet takes less than a minute, and we find that the sequence is in the OEIS. The page for the sequence tells us that the growth rate is $\Theta(\frac{1}{i^{1/2}}(3+2\sqrt{2})^i)$.

Answer 2

Here's the correct recurrence for the running time of rec: $$ f(i,j) = \begin{cases} O(1), & i = 0 \text{ or } j = 0, \\ f(i-1,j) + f(i,j-1) + f(i-1,j-1) + O(1), & \text{otherwise}. \end{cases} $$ The running time of the entire program is $f(n,n) + O(n^2)$. Now it remains to solve the recurrence for $f,ドル which I leave to you.

Answer 3

You are interested in the time rec(i, j) takes. If you look at the code, it doesn't depend on the contents of the l array, just on i and j. Just take each call to take time 1. Then, by the recursion, for the time $t_{i j}$ you have the recurrence: $$ t_{i + 1, j + 1} = t_{i + 1, j} + t_{i, j + 1} + t_{i, j} \quad t_{i, 0} = t_{0, j} = 1 $$ Use generating functions to solve this. Define: $$ T(x, y) = \sum_{\substack{i \ge 0 \\ j \ge 0}} t_{i j} x^i y^j $$ Then $T(x, 0) = \frac{1}{1 -x},ドル $T(0, y) = \frac{1}{1 - y}$. Using the properties of generating functions: $$ \frac{T(x, y) - y / (1 - x) - x / (1 - y) + 1}{x y} = \frac{T(x, y) - x / (1 - y)}{x} + \frac{T(x, y) - y / (1 - x)}{y} + T(x, y) $$ This gives $T(x, y) = \frac{1 - x - y}{1 - x - y - x y}$. Luckily we aren't interested in $t_{i j},ドル just in $t_{n n}$: $$ \begin{align*} [x^n y^n] T(x, y) &= [x^n y^n] \left(1 + \frac{x y}{1 - x - y - x y}\right) \end{align*} $$ Let's tackle the second term: $$ \begin{align*} [x^n y^n] \frac{x y}{1 - x - y - x y} &= [x^{n - 1} y^{n - 1}] \frac{1}{1 - x - y - x y} \end{align*} $$ Expanding each term of the geometric series by the multinomial theorem: $$ \begin{align*} [x^{n - 1} y^{n - 1}] \frac{1}{1 - x - y - x y} &= [x^{n - 1} y^{n - 1}] \sum_{k \ge 0} \sum_{\substack{r \ge 0 \\ s \ge 0}} \binom{k}{r ,円 s ,円 k - r - s} x^r y^s (x y)^{k - r - s} \\ &= [x^{n - 1} y^{n - 1}] \sum_{k \ge 0} \sum_{\substack{r \ge 0 \\ s \ge 0}} \binom{k}{r ,円 s ,円 k - r - s} x^k y^k \\ &= \sum_{\substack{r \ge 0 \\ s \ge 0}} \binom{n - 1}{r \; s \; n - 1 - r - s} \\ &= 3^{n - 1} \end{align*} $$ This gives a complexity of $O(3^n)$.

Edits: I had messed up badly, I hope it is fixed now.

• Peter Shor: Something is wrong. The run time is $O(n^2)$ with memoization (which the OP described as cheating in a comment). Without memoization, the run-time is exponential. This generating function argument should give you the answer without memoization, but clearly you've made a mistake.
• Yuval Filmus: It's not true that the coefficient of $x^ny^n$ in $T(x,y)$ is the same as the coefficient of $x^{2n}$ in $T(x,x)$: the latter is much larger. Also, you have an algebra mistake, 1ドル-2x-x^2 \neq (1-x)^2$. The smallest (in magnitude) root of 1ドル-2x-x^2$ is $\sqrt{2}-1,ドル so the growth rate of the coefficient of $x^n$ is roughly $[1/(\sqrt{2}-1)]^n = (\sqrt{2}+1)^n$. This gives us the approximation $(3+2\sqrt{2})^n$ for the coefficient of $x^{2n}$ in $T(x,x)$. This approximation is true up to polynomial factors, since $T(x,z-x)$ is maximized for $z=2x$. It also agrees with Peter Shor's answer.
• vonbrand: You are right, I'm fixing the derivation. It turned out harder than I thought.
• DenLilleMand: reallyreallyreallyreally