The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
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}$
asked in Set Theory & Algebra by Veteran (99k points) | 133 views

2 Answers

0 votes
Its better to take an example and trace.

The answer comes out to be (d).
answered by Active (1.3k points)
0 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)
answered by (171 points)
edited by

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,065 questions
36,871 answers
91,628 comments
34,760 users