864 views
4 votes
4 votes

If k is a non-negative constant, then the solution to the recurrence
$T(n) = \begin{cases}  1 & \quad n=1 \\ 3T(n/2) + n & \quad n>1 \end{cases} $

for $n$, a power of 2 is 

  1. $T(n) = 3^{\log_2 n} - 2n$
  2. $T(n) = 2 \times 3^{\log_2 n} - 2n$
  3. $T(n) = 3 \times 3^{\log_2 n} - 2n$
  4. $T(n) = 3 \times 3^{\log_2 n} - 3n$

5 Answers

Best answer
6 votes
6 votes

Option (C).

Since N is a power of 2, $n = 2^{k}$ which implies, $k = log_2 n$,

Using recursion tree method,

$T(n) = n + n * \frac{3}{2} + n * \big(\frac{3}{2}\big)^2 +.... + n * \big(\frac{3}{2}\big)^k$

There are $k+1$ terms in this GP series therefore,

$T(n) = n * \frac{\big(\frac{3}{2}\big)^{k+1} - 1}{\frac{3}{2} - 1}$

Substituting $k = \log_2 n$, we get,

$T(n) = 2n * \big[\frac{3}{2} * \big(\frac{3}{2}\big)^{\log_2 n} - 1\big]$

simplification gives, $T(n) = 3.3^{\log_2 n} - 2n$

selected by
10 votes
10 votes
Answer verification is much more easier than solving.
T(1) = 1, T(2) = 5

Just put n = 2 option C gives 5.
2 votes
2 votes

If we solve by just checking small values then it will be easy otherwise we have to solve recurrence as above.

1 votes
1 votes

The Recurrence T(N) = 3T(N/2) + cN and T(1) = 1 .

N is a power of 2, so, N = 2and K = Log N

Total time at 1st level :--> cN 

Total time at 2nd level :--> 3(cN/2) = (3/2)cn 

Total time at 3rd level :--> 32(cn/22) = (3/2)2cn

...........

........

............

Total Time Complexity => $\left \{ 1 + 3/2 + (3/2)^{2} + ... + (3/2)^{K - 1} \right \} cN + N^{Log 3}$

=> $\left \{ 1 * (3/2)^{K - 1}) / (3/2-1) \right \} cN + N^{Log 3}$

=> $\left \{ 2c + 1 \right \} N^{Log 3} - 2cN$

Take c = 1

=> $3 * 3^{Log N} - 2N$

Option C is correct .

Answer:

Related questions

2 votes
2 votes
2 answers
1
Bikram asked Oct 4, 2016
346 views
$$T(n) = \begin{cases} 4 & \quad if \: \: n =1 \\ T(n-1) + 4 & \quad otherwise \end{cases}$$Value of $T(1000)$ is ___
2 votes
2 votes
2 answers
2
Bikram asked Oct 4, 2016
546 views
Consider the following recurrence relation.$$T(n) = \begin{cases}1 & \quad if \: n = 1 \\ T(n-1) + 2^n \quad & otherwise \end{cases}$$What will be the value of $T(10)$?