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(n2). 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, n2) + T(n, n-12) + T(n-12, n-12) 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&1cr 1&2&3&4&5cr 1&3&6&10&15cr 1&4&10&20&351&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+2sqrt{2})^i)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/9162 Ask a Question Download Related Notes/Documents
