The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+23 votes

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

- $2^k$
- $\frac{(3^{k+1}-1)}{2}$
- $3^{\log_2 k}$
- $2^{\log_3 k}$

+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

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$

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

+45 votes

Best answer

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

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

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) ?

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.

@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 ?

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

Now, whatever be it, Master theorem just gives the asymptotic bound- here the question asks for the exact value.

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

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

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.

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

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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.1k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.3k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4k
- Non GATE 1.4k
- Others 1.5k
- Admissions 556
- Exam Queries 553
- Tier 1 Placement Questions 23
- Job Queries 69
- Projects 18

47,903 questions

52,285 answers

182,209 comments

67,715 users