11,773 views
35 votes
35 votes

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

2 Answers

Best answer
78 votes
78 votes

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
5 votes
5 votes
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
Answer:

Related questions

47 votes
47 votes
7 answers
1
Kathleen asked Sep 15, 2014
17,728 views
The running time of the following algorithmProcedure $A(n)$If $n \leqslant 2$ return ($1$) else return $(A( \lceil \sqrt{n} \rceil))$;is best described by$O(n)$$O(\log ...
18 votes
18 votes
5 answers
3
30 votes
30 votes
1 answer
4
Kathleen asked Sep 15, 2014
7,762 views
Let $f(A,B) = A'+B$. Simplified expression for function $f(f(x+y, y), z)$ is$x' + z$$xyz$$xy' + z$None of the above