edited by
2,311 views
15 votes
15 votes

Let $T(a, b)$ be the function with two arguments (both nonnegative integral powers of 2) defined by the following recurrence:

  • $ T(a, b) = T \left( \frac{a}{2}, b \right) +T\left( a, \frac{b}{2} \right)\quad \quad \quad \text{if } a, b \geq 2$;
  • $ T(a, 1) = T \left( \frac{a}{2}, 1 \right) \quad \quad \quad\quad\quad \quad \quad \:\:\:\text{if } a \geq 2$;
  • $ T(1, b) = T \left( 1, \frac{b}{2} \right) \quad \quad \quad\quad \quad\quad\quad \quad \text{if } b \geq 2$;
  • $T(1, 1)=1$.

What is $T(2^r, 2^s)$?

  1. $rs$
  2. $r+s$
  3. $\begin{pmatrix} 2^r+2^s \\ 2^r \end{pmatrix}$
  4. $\begin{pmatrix} r+s \\ r \end{pmatrix}$
  5. $2^{r-s}$ if $r \geq s$, otherwise $2^{s-r}$
edited by

4 Answers

Best answer
19 votes
19 votes

Value of $T(2^r,2^s)$ is nothing but the number of leaf nodes in its recursion tree. The reason for this is that there is only one base condition $T(1,1)$ which returns $1$ which are all ultimately added. Here is an example recursion tree for $T(2^2,2^3)$.

We will try to use some combinatorial technique to count the number of leaf nodes. One way of counting the number of leaf nodes in the recurrence tree is by counting all possible paths that one can take from the root to the leaf node. The reason for doing this would be clear in a moment. This idea would be used to establish a link with a very common combinatorial problem.

Claim: If we consider a grid of size $r \times s$ then the possible paths from $(r,s)$ to $(0,0)$ in that grid such that we can either move backwards or downward is nothing but all possible paths in recurrence tree from the root node to leaf node.

This happens to be true because arguments of recurrence relation are in powers of two, and at each level of recurrence tree, the power of one of the arguments get reduced by one.

$$\begin{align} T(2^r, 2^s) &= T(2^{r-1},2^s) + T(2^r, 2^{s-1}) \\ T(1,2^s) &= T(1,2^{s-1}) \\ T(2^r,1) &= T(2^{r-1},1) \\ T(1,1) &= 1 \\ \end{align}$$Continuing from our previous example here is a grid of size $2 \times 3$ with two valid paths highlighted.

The number of valid paths possible in this grid will give us the count of the number of leaf nodes in the recurrence tree. Interestingly this problem, when interpreted exactly in opposite way, happens to be a very well known problem of combinatory.

In a grid of size $r \times s$, count the number of possible paths from $(0,0)$ to $(r,s)$ such that we can either move forward(F) or upward(U).

So there are $\binom{r+s}{r}$ many different valid paths on this grid to reach $(r,s)$ from $(0,0)$ or vice versa. And in turn, there are same numbers of leaf nodes in the recursion tree. Therefore, we can conclude with - $$T(2^r,2^s) = \binom{r+s}{r}$$

edited by
6 votes
6 votes

Say for $T(4,2)=T(2^{2},2^{1})$ answer should be $\binom{2+1}{1}=3$

Now try with recursion tree

$T(4,2)=T(2,2)+T\left ( 4,1 \right )$

$T(2,2)=T(2,1)+T\left ( 1,2 \right )=1+1=2$

 

So, $T(4,2)=T(2,2)+T\left ( 4,1 \right )=2+1=3$

Answer Matched


Take another one $T(8,4)=T(2^{3},2^{2})$

So, according to option answer should be $\binom{3+2}{2}=10$

Now try with recurrence tree

$T\left ( 8,4 \right )=T\left ( 4,4 \right )+T\left ( 8,2 \right )$

 

$T\left ( 4,4 \right )=T\left ( 4,2 \right )+T\left ( 2,4 \right )$

 

$T\left ( 4,2 \right )=T\left ( 2,2 \right )+T\left ( 4,1 \right )$

                  $=T\left ( 2,1 \right )+T\left ( 1,2 \right )+T\left ( 4,1 \right )=3$

 

$T\left ( 2,4 \right )=T\left ( 2,2 \right )+T\left ( 1,4 \right )=T\left ( 2,1 \right )+T\left ( 1,2 \right )+T\left ( 1,4 \right )=3$

 

$T\left ( 8,2 \right )=T\left ( 4,2 \right )+T\left ( 8,1\right )=3+1=4$

 

Then, $T\left ( 8,4 \right )=T\left ( 4,4 \right )+T\left ( 8,2 \right )=6+4=10$

Again it is matched with option

Ans $D)$

2 votes
2 votes
let l=2^r and m=2^s

so the recurrence relation becomes

T(l,m) = T(l-1,m)+T(l,m-1)

T(l,0)  = T(l-1,0)

T(0,m)=T(0,m-1)

solving recurrence for any non-negative l,m we get

T(l,m) =T(l-1,m)+T(l,m-1)

           =T(l-2,m)+2*T(l-1,m-1)+T(l,m-2)

           =T(l-3,m)+3*T(l-2,m-1)+3*T(l-1,m-2)+T(l,m-3)
NOTE: assume initially l=m
Thing here to note is the coefficients are following the pascal triangle(corresponding to the difference in a and b) as shown below T(a,b) i.e. a is the first input  b is the second

 a-b =                                          -3     -2     -1    0    1     2    3

                                                                           1

                                                                     1          1

                                                            1             2           1

                                                     1              3           3          1  

and so on

by value putting  T(0,0)=1,T(1,0)=1,T(0,1)=1,T(1,1)=2

we get to know these  form solution to the following triangle

                                                                           T(0,0)

                                                               T(0,1)            T(1,0)

                                                        T(0,2)         T(1,1)           T(2,0)

                                                 T(0,3)       T(1,2)             T(2,1)         T(3,0)

hence we conclude T(l,m)=C(l+m,l)
edited by
1 votes
1 votes
Its better to take an example and trace.

The answer comes out to be (d).
Answer:

Related questions

22 votes
22 votes
3 answers
4