2.9k views

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

1. $2^k$
2. $\frac{(3^{k+1}-1)}{2}$
3. $3^{\log_2 k}$
4. $2^{\log_3 k}$
0
how to solve this recurrence equation ?
0
Very Good Question. Observe what is asked in the question.
+14

Trace the pattern:
$T(2^0) = 1$
$T(2^1) = 3*T(2^0) + 1 = 4$
$T(2^2) = 3*T(2^1) + 1 = 13$
$T(2^3) = 3*T(2^2) + 1 = 40$

put these values in the options.

B. $\frac{3^{k+1} -1}{2}$
$T(2^0) = (3^1 -1)/2 = 1$
$T(2^1) = (3^2 -1)/2 = 4$
$T(2^2) = (3^3 -1)/2 = 13$
$T(2^3) = (3^4 -1)/2 = 40$

Hence, (B) is the correct option.

0
@Manu tracing pattern is good but in exam can we also do this by putting 2^k as 'x' and then Solving it by master method.
0
@sandeep they haven't asked time Complexity, right?
0

how this comes, please explain the logic or any formulae

It would be really easy to understand

https://gateoverflow.in/?qa=blob&qa_blobid=9620849864640559057

0
@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$

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}$

edited by
0
Sir plz chk calculation

T(x)= = $3^{k} + \frac{3^{\log_2 {2^k}-1} - 1}{3-1}$

So, direct value I think not possible
0
@arjun sir  , In master method what is the value of e ?  Why  did u take it as 0 ?

e > 0  is the condition , right ?   Will it not be O(3^k  / 2^k) ?
0
@srestha which step is wrong? :O

@Dq $\epsilon > 0$, isn't it obvious in that statement? I did not take it as 0.
0
@arjun sir ,

$T(x)=3T(\frac{x}{2})+1$

We can apply Master theorem case $1 a=3 b=2 \epsilon=1$
\begin{align*} \\ f(x) & =1 \text{ is } O(x^{\log_2 3 - \epsilon }) \\ & = O(x^{(\log_2 3 )- 1 }) \\ & = O(\frac{x^{ \log_2 3}}{x}) \\ &= O(\frac{(2^{k})^{\log_2 3}}{2^{k}}) & \text{ substitute x= } 2^{k} \\ &= O(\frac{3^{k}}{2^{k}}) \end{align*}

What is wrong with this ? What is the $\epsilon$ you took ?
+2
:O I just showed that a positive $\epsilon$ exists- which is required for Master theorem. Why did you find its value? If a positive $\epsilon$ exists, then we can directly apply case 1- big O is not good, Master theorem says $\Theta$ which is more precise.

Now, whatever be it, Master theorem just gives the asymptotic bound- here the question asks for the exact value.
+1
Got it. Thank you sir :)
0
@Arjun Sir Chk this.

in ur 2nd calculation

$T(x) = 3T\left(\frac{x}{2}\right) + 1\\= 9T \left (\frac{x}{4}\right) + 1 + 3 \\ \dots \\= 3^{\log_2 2^k} + \left( 1 + 3 + 9 + \dots + 3^{\log_2 {2^k-1}}\right)$

here last term is $3^{\log_2 {2^k-1}}$ , rt?

Addition of G.P. series S=$a\frac{r^{n}-1}{r-1}$

So, T(x)= = $3^{k} + \frac{3^{\log_2 {2^k}-1} - 1}{3-1}$

direct value I think not possible
0
No, 'n' is the number of terms. "-1" goes from it as first term is 3^0.
0
wah arjun sir u provide bunch of methods nice
0
wao #Arjun sir you are awesome.
0
sir just a little doubt , when you solve it by using master theoram and you get

Θ(3k) so from this how you can conclude only possible ans is B. plz clear this doubt.
0
$T(2^k)=3T(2^{k-1})+1$

Let $T(2^k)=S_b$

Retranslating recurrence

$S_b=3S_{b-1}+1$..(1)

Homogenous solution=$\alpha3^b$

Particular solution $=d$

Subsituting particular solution form in (1)

$d=3d+1$

$d=-1/2$

Full solution is $S_b=\alpha3^b-\frac{1}{2}$

Initial condition $T(1)=1=>T(2^0)=1$

So $b=0,S_0=1$

$1=\alpha-\frac{1}{2}=>\alpha=\frac{3}{2}$

$S_b=3^{b+1}/2-1/2=\frac{3^{b+1}-1}{2}$

Change variables

$T(2^k)=\frac{3^{k+1}-1}{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
0

it will be

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

1
2