2 votes 2 votes . 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 sumit goyal 1 asked Jul 7, 2017 sumit goyal 1 556 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes You must need a stopping condition i.e base condition for solving a recurrence relation. junaid ahmad answered Jul 7, 2017 junaid ahmad comment Share Follow See 1 comment See all 1 1 comment reply sumit goyal 1 commented Jul 7, 2017 reply Follow Share thnks bhai 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes https://gateoverflow.in/128456/solve-the-recurrence-using-iteration-method#a128478 Aashish S answered Jul 7, 2017 Aashish S comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments sumit goyal 1 commented Jul 7, 2017 reply Follow Share . BHAI answer iska nlogn ayega #can u solve this iam not getting answer thanks 1 votes 1 votes Aashish S commented Jul 8, 2017 reply Follow Share 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 0 votes 0 votes sumit goyal 1 commented Jul 8, 2017 reply Follow Share thanksss 1 votes 1 votes Please log in or register to add a comment.