The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
2k 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}$
asked in Algorithms by Veteran (59.4k points) | 2k views
0
how to solve this recurrence equation ?
0
Very Good Question. Observe what is asked in the question.
+7

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?

2 Answers

+34 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\\= 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)\\ \left(\text{recursion depth is }\log_2 x \text{ and } x = 2^k\right) \\= 3^{k} + \frac{3^{\log_2 {2^k}} - 1}{3-1} \\ \left(\text{Sum to n terms of GP with } a = 1 \text{ and } r = 3 \right)\\=3^k + \frac{3^k - 1}{2}  \\=\frac{3. 3^k - 1}{2} \\=\frac{3^{k+1} -1}{2} $



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

answered by Veteran (339k points)
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.
+1 vote
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
answered by Junior (949 points)
0

it will be

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



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,770 questions
41,729 answers
118,874 comments
41,381 users