in Algorithms
498 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$
in Algorithms
by
498 views

5 Answers

6 votes
6 votes
Best answer

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

1 comment

@Bikram Sir,

@Arjun Sir,

3T(n/2)+n

here when we will solve from recurrence relation then 

the term "n" in the above relation is responsible for generating the above GP series as mentioned in the question which results as 

2n∗[3/2∗(3/2)log2n−1]

and 

3T(n/2) is responsible for generating 3^k and at last k = log2n which will become 3log2n

but at last where is 3log2n

please explain...

0
0
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 Comments

ya u r ri8....

but after solving answer comes option (A).

can anyone solve this ?????
1
1
gr8 bhai your way of solving  are really awesome
0
0
1 vote
1 vote

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 .

by

3 Comments

can u please explain how N^log 3 appeared ?

and little more explaination on how u evaluated that series will be helpful...
3
3
edited by
As per master's method, $T(n) = O(n^{\log_2 3})$, but why it has been added in this recusrsion tree approach, I am not sure. Also, the sum of GP series will be $\frac{1*\big((\frac{3}{2})^{k} - 1\big)}{\frac{3}{2} - 1}$, since there are $k$ terms in the series.
0
0
plz explain this in more simple way
0
0
1 vote
1 vote

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

Answer:

Related questions