I want to know an estimate of $a_{i, j}$

Question

Let $$ a_{ij} = \begin{cases} -1, & \text{if $i = -1$ and $j = -1$} \\ 1, & \text{if $i = -1$ and $j \ne -1$} \\ 1, & \text{if $i \ne -1$ and $j = -1$} \\ a_{i-1, j-1} + a_{i-1, j} + 1, & \text{if $i \ne -1$ and $j \ne -1$}. \\ \end{cases} $$ Then $a_{i, j}$ is defined for the integers $i \ge -1$ and $j \ge -1$ as above.

I want to know a good lower bound and a good upper bound of $a_{i, j}$.

I want to know the answer of a problem from the following site: http://algs4.cs.princeton.edu/11model/

The problem is:

Estimate the number of recursive calls that would be used by the following code to compute binomial$(100, 50, 0.25)$. I know that $a_{100, 50}$ is the exact number of the recursive calls.

public static double binomial(int N, int k, double p) {

if (N == 0 && k == 0) return 1.0; 

if (N < 0 || k < 0) return 0.0; 

return (1.0 - p) *binomial(N-1, k, p) + p*binomial(N-1, k-1, p); 

} 

Here is my estimate:

$2^0 + 2^1 + \dots + 2^{51} = 2^{52} - 1 <$ the number of recursive calls $< 2^0 + 2^1 + \dots + 2^{101} = 2^{102} - 1$.

I'm sorry for my poor English.

Please advise.

Answer 1

I wrote a C++ program and got the following result

$$a(2i+1,i) = \{3, 15, 63, 255, 1023\}=4^{i+1}-1,i:=0..4; $$

That was the first dependency I've noted after $a(i,i) = 2^{i+2}-3$.

So, I think that

$$a(101,50)=4^{51}-1=2^{102}-1$$

Consider $a(i,j) < a(i+1,j)$ $=>$ $a(100,50) < 2^{102}-1$

I think you can estimate lower bound using the fact $a(i,j) < a(i+1,j+1)$ and same formula.

Answer 2

Fist thing, the recursive algorithm is really inefficient for this kind of problem.

Second thing, to bound $a_{ij}$ :

• If $j>i$, then $a_{i,j} = a_{i,i+1}$

Recursively, $a_{i,i+1} = 2^{i+2}-1$

• If $j\leq i$, then $a_{i,j} \leq a_{i,i+1}$

And recursively, $a_{i,j} \geq 2\binom{i+2}{j+1}-1$