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

thnks very helpful  :))

---

hi bro in that link it will be  3T(N/4)  ?

---

yes it should be 3T(N/4) in question but in recurrence relation its solve in that manner..

Hope the following link also help

http://www.cs.yale.edu/homes/aspnes/pinewiki/SolvingRecurrences.html (See 2.2 Backward Subsitution)

https://gateoverflow.in/65709/%23recurrence-relation

---

.

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