Example for the analysis of a recursive function

````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.

-

$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 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. – moller1111 Jan 26 at 1:50
Do you want the time bounds with or without memoization? – Peter Shor Jan 26 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 at 5:53

3 Answers

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

-

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.

-

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.

-

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 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 at 18:49
You are right, I'm fixing the derivation. It turned out harder than I thought. – vonbrand Jan 26 at 19:18
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 34, "mathjax_display_tex": 9, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.932433009147644, "perplexity_flag": "head"}