0 votes 0 votes T (n) = T (n/2) + 2n Using Master's Method What is the Complexity Of This Recurrence Relation? Or Using AnyOther Method? Algorithms algorithms recurrence-relation time-complexity master-theorem + – pradeepchaudhary asked Aug 20, 2018 • edited Aug 20, 2018 by pradeepchaudhary pradeepchaudhary 924 views answer comment Share Follow See all 5 Comments See all 5 5 Comments reply MiNiPanda commented Aug 20, 2018 reply Follow Share The generic form of master theorem. T(n) = aT(n/b) + f(n) So this equation matches with that. https://brilliant.org/wiki/master-theorem/ Here see the 3rd case. This equation matches with it because f(n)=2n and it is Omega(nlogba+Epislon) i.e. 2n>nlogba+Epislon where a=1,b=2. + check the additional condition a(fn/b)<=f(n). This is also satisfied. 1*f(n/2) = 2n/2<=2n So, T(n) = Theta(2n ) 3 votes 3 votes Prashant. commented Aug 20, 2018 reply Follow Share Vikas check Minipanda answer she is correct . 1 votes 1 votes Verma Ashish commented Aug 31, 2018 reply Follow Share how can u apply master's theorem if it is not in the form of msters theorem?? 0 votes 0 votes MiNiPanda commented Aug 31, 2018 reply Follow Share It's in the form..that is what i stated in the comment..have a look.. also visit the link for details.. 0 votes 0 votes Verma Ashish commented Aug 31, 2018 reply Follow Share ma'm it is basic masters theorem. plese clear my doubt-- https://gateoverflow.in/235523/masters-theorem 0 votes 0 votes Please log in or register to add a comment.
