0 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 1.5k views answer comment Share Follow Print See all 5 Comments 5 5 Comments reply MiNiPanda commented Aug 20, 2018 reply Follow flag 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 3 replyShare Prashant. commented Aug 20, 2018 reply Follow flag Vikas check Minipanda answer she is correct . 1 1 replyShare Verma Ashish commented Aug 31, 2018 reply Follow flag how can u apply master's theorem if it is not in the form of msters theorem?? 0 0 replyShare MiNiPanda commented Aug 31, 2018 reply Follow flag It's in the form..that is what i stated in the comment..have a look.. also visit the link for details.. 0 0 replyShare Verma Ashish commented Aug 31, 2018 reply Follow flag ma'm it is basic masters theorem. plese clear my doubt-- https://gateoverflow.in/235523/masters-theorem 0 0 replyShare Please log in or register to add a comment.
