498 views

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$

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$

### 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

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

Just put n = 2 option C gives 5.

ya u r ri8....

but after solving answer comes option (A).

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

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

can u please explain how N^log 3 appeared ?

and little more explaination on how u evaluated that series will be helpful...
edited
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.
plz explain this in more simple way

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