algorithm

Question

. T (n) = 3T (n/2) + n

 

i can apply masters theorem and solve it , can  i solve it by back substitution too , but i dont know base condition ??? how can i solve it

Answer 1

You must need a stopping condition i.e base condition for solving a recurrence relation.

Comments

thnks bhai

Answer 2

https://gateoverflow.in/128456/solve-the-recurrence-using-iteration-method#a128478

Comments

.

BHAI  answer iska  nlogn ayega #can u solve this  iam not getting answer thanks

---

U are correct. bro.

just at 2nd last step its n + n + n + ...... n ( k times)

therefore

=>   2^k * T(1) + n + n + n + ...... n ( k times)

=>  2^k * T(1) + k*n  --(1)

& T(1) means when n=2^k ..

Put back 2^k=n in equation (1) here

=> n + k*n

=>n(1+k)

=>ignoring 1 => n*k  ----(2)

=>if 2^k=n then k=logn ... put back in eq(2) here

=>nlogn

---

thanksss