[Solved]: Example for the analysis of a recursive function

Problem Detail: 

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.

Asked By : Schwammkopf

Answered By : Peter Shor

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)$.

Best Answer from StackOverflow

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

 Ask a Question

 Download Related Notes/Documents