133 views

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

• $T(a, b) = T \biggl( \frac{a}{2}, b \biggl) +T\biggl( a, \frac{b}{2} \biggl) \quad \quad \text{ if } a, b \geq 2$;
• $T(a, 1) = T \biggl( \frac{a}{2}, 1 \biggl) \quad \quad \quad \text{ if } a \geq 2$;
• $T(1, b) = T \biggl( 1, \frac{b}{2} \biggl) \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}$

Its better to take an example and trace.

The answer comes out to be (d).
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)