GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
98 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 (87.4k points)   | 98 views

1 Answer

0 votes
Its better to take an example and trace.

The answer comes out to be (d).
answered by Active (1k points)  

Related questions



Top Users Sep 2017
  1. Habibkhan

    8312 Points

  2. Warrior

    2862 Points

  3. rishu_darkshadow

    2796 Points

  4. Arjun

    2766 Points

  5. A_i_$_h

    2526 Points

  6. manu00x

    2094 Points

  7. nikunj

    1980 Points

  8. Bikram

    1874 Points

  9. makhdoom ghaya

    1810 Points

  10. SiddharthMahapatra

    1718 Points


26,283 questions
33,842 answers
80,383 comments
31,193 users