+1 vote
84 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).