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.

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.