The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+8

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

+36 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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.9k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 448
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

37,976 questions

45,471 answers

131,383 comments

48,425 users