Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
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.

share|improve this question
    
$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. –  saadtaame Jan 26 '13 at 1:25
    
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. –  Hasan Tahsin Jan 26 '13 at 1:50
    
Do you want the time bounds with or without memoization? –  Peter Shor Jan 26 '13 at 4:20
    
@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... –  vonbrand Jan 26 '13 at 5:53

3 Answers 3

up vote 5 down vote accepted

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
1  
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. –  Peter Shor Jan 26 '13 at 17:05
    
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. –  Yuval Filmus Jan 26 '13 at 18:49
    
You are right, I'm fixing the derivation. It turned out harder than I thought. –  vonbrand Jan 26 '13 at 19:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.