31 views
Solve the Given Recurrence using the Substitution method (in book it was Recursion Tree method)

T(n) = 3T(n/2) + n
| 31 views

$T(n)=3T\left ( \dfrac{n}{2} \right )+n$

$\downarrow$

$3\left [3.T\left ( \dfrac{n}{2^2} \right )+\dfrac{n}{2} \right ]+n=3^2T\left ( \dfrac{n}{2^2} \right )+\left ( \dfrac{3}{2} \right )n+n$

$\downarrow$

$3^2\left [3.T\left ( \dfrac{n}{2^3} \right )+\dfrac{n}{2^2} \right ]+\left ( \dfrac{3}{2} \right )n+n=3^3T\left ( \dfrac{n}{2^3} \right )+\left ( \dfrac{3}{2} \right )^2n+\left ( \dfrac{3}{2} \right )n+n$

.

.

$3^kT\left ( \dfrac{n}{2^k} \right )+\left ( \dfrac{3}{2} \right )^{k-1}n+\left ( \dfrac{3}{2} \right )^{k-2}n\ +. . . .+n$

$Now:$

$\dfrac{n}{2^k}=1$

$k=log_{2}n$

$3^{log_2{n}}.T(1)+n\left [ \left ( \dfrac{3}{2} \right )^0+\left ( \dfrac{3}{2} \right )^1+\left ( \dfrac{3}{2} \right )^2+. . . . . .\left ( \dfrac{3}{2} \right )^{k-1} \right ]$

$n^{log_{2}3}+n\left [ \dfrac{\left ( \dfrac{3}{2} \right )^k-1}{\dfrac{3}{2}-1} \right ]$

$n^{log_{2}3}+n\left [ \dfrac{\left ( \dfrac{3}{2} \right )^{log_{2}n}-1}{\dfrac{3}{2}-1} \right ]$

$n^{log_{2}3}+2n\left [ \left ( \dfrac{3}{2} \right )^{log_{2}n}-1 \right ]$

$n^{log_{2}3}+2n\left [ \left ( n \right )^{log_{2}(3/2)}-1 \right ]$

$n^{log_{2}3}+2n\left [ \left ( n \right )^{log_{2}3-log_{2}2}-1 \right ]$

$n^{log_{2}3}+2\left [ \left ( n \right )^{log_{2}3-1+1}-n \right ]$

$Ans: 3n^{log_{2}3}-2n$

by (415 points)
selected by
0
small mistake at the end.
0

@ankitgupta.1729

What is that sir? Correct it if possible.

0
bhai, answer should be $3n^{\log_2 3 } - 2n.$ right ?
0
Yes, you are right. I just wrote the TC instead of complete answer.