GATE CSE 2002 | Question: 1.3

Question

The solution to the recurrence equation $T(2^k) = 3T(2^{k-1})+1, T(1) =1$ is

• A. $2^k$
• B. $\frac{(3^{k+1}-1)}{2}$
• C. $3^{\log_2 k}$
• D. $2^{\log_3 k}$

Comments

@pooja , It is simply $a^{log_{a}x} = x$ . you can remember it as a formula or it is also not hard to prove.. assume  $a^{log_{a}x} = y$ , take log both sides with base as '$a$' . So, it becomes $log _{a}[a^{log_{a}x}] = log_{a}y$

$\Rightarrow log_{a}x * log_{a}a = log_{a}y$

$\Rightarrow log_{a}x = log_{a}y$

$\Rightarrow log_{a}x - log_{a}y = 0$

$\Rightarrow log_{a}(\frac{x}{y}) = 0$

$\Rightarrow \frac{x}{y} = 1$

$\Rightarrow y=x$

---

Other way: convert the given recurrence relation to the relation like we do in discrete mathematics

$a(2^k) = 3a(2^k/2) + 1$

For first option we can write it as $a(2^k) = 2^k$ , here we will check optionwise which gets us a(1) = 1.

here in each option we should put k as 0. By checking optionwise we will get A and B option same, then we will check for a(2), puttiing in the reccurence relation (taking k as 1) ,   a(2) = 4

checking between A and B we will get option A as 2 and option B as 4

So, finally B option is correct

---

Done ✅

Answer 1

Let $x = 2^k$
$T(x) = 3T\left(\frac{x}{2}\right) + 1$
We can apply Master's theorem case 1 with $a = 3$ and $b = 2$ as $f(x) = 1 = O\left(x^{\log_2 3 - \epsilon} \right), \epsilon > 0 $

So, $T(x) = \Theta \left(x^{\log_2 3}\right)  \\= \Theta \left( {2^k}^{\log_2 3} \right)\\= \Theta \left({2^{\log_2 3}}^k \right)\\ = \Theta \left(3^k \right)$

So, only option possible is B.

---

We can also directly solve as follows:

$T(x) = 3T\left(\frac{x}{2}\right) + 1$
$\\\quad= 9T \left (\frac{x}{4}\right) + 1 + 3$
$ \\\quad \vdots$
$ \\\quad= 3^{\log_2 2^k} + \left( 1 + 3 + 9 + \dots + 3^{\log_2 {2^k-1}}\right)$
$\\\quad \left(\text{recursion depth is }\log_2 x \text{ and } x = 2^k\right)$
$ \\\quad= 3^{k} + \frac{3^{\log_2 {2^k}} - 1}{3-1}$
$ \\\quad \left(\text{Sum to n terms of GP with } a = 1 \text{ and } r = 3 \right)$
$\\\quad =3^k + \frac{3^k - 1}{2}$
$\\\quad=\frac{3. 3^k - 1}{2}$
$\\\quad=\frac{3^{k+1} -1}{2} $

---

OR
 
$T\left(2^k\right) = 3T\left(2^{k-1}\right) + 1$
$ \\\quad= 3^2T\left(2^{k-2}\right) + 1 +3$
$ \quad\vdots$
$ \\\quad= 3^k T\left(2^{k-k}\right) + \left( 1 + 3 + 9 + \dots + 3^{k-1}\right)$
$ \\\quad \left(\text{recursion depth is }k\right)$
$\\\quad= 3^k + \frac{3^{k -1}} {3-1}$
$\\\quad\left(\text{Sum to n terms of GP with } a = 1 \text{ and } r = 3 \right)$
$\\\quad=3^k + \frac{3^k -1}{2}$
$\\\quad=\frac{3. 3^k - 1}{2}$
$\\=\frac{3^{k+1} -1}{2}  $

Comments

how you @Ayush Upadhyaya did using this approach can you provide soem resource to see more such kind of problems . here you have assumed that 2^k an din Sb b= k ???

---

using change of variable method

---

nice , thank you!

Answer 2

As other than the recursion function , any function of K is not added , this equation is equivalent to  T(k) = 3T(k-1) + 1  , T(0) = 1

Using repeated substitution we can observe that    T(k) = 1 + 3^1 + 3^2 ... + 3^k .

Using geometric series summation   T(n)  = (3^(k+1) - 1)/2

Comments

it will be

T(k)=3T(k/2)+1

---

he used log inside the function.so log(2^(k-1)) =k-1

Answer 3

Solving by Substitution-

$T(2^k)=3T(2^{k-1})+1$

           $=3[3T(2^{k-2})+1]+1$

           $=3^2T(2^{k-2})+3+1$

           .

           .

           .

          $=3^xT(2^{k-x})+3^{x-1}+3^{x-2}+3^{x-3}.......+3^2+3^1+3^0$

now base condition is $T(1)=1$,

Therefore, $T(2^0)=1$ and we have $T(2^{k-x})$
Thus, comparing the powers, we get

$k-x=0$

$k=x$

Substituting it again in the recurrence we get-

          $=3^k+3^{k-1}+3^{k-2}.......+3^2+3^1+3^0$

Now this is GP. Common ratio = 3, first term =1, total terms =k+1

Thus, $\frac{3^{k+1}-1}{2}$ --ANSWER.

Answer 4

Look at the explanation it's very simple , option B is correct

Answer 5

You can take K values like K=1 and substitute in equation as well as options.