1 votes 1 votes On which of the following recurrence relation Master Theorem cannot be applied? A. T(n)=2T(n/2)+nlogn B. T(n)=T(n/2)+1 C. T(n)=8T(n/2)+logn D. T(n)=7T(n/4)+n2 I think we can apply on all. But plz correct me with reason.Thanks Algorithms algorithms recurrence-relation master-theorem + – Rajesh Pradhan asked Oct 14, 2016 • edited Jun 23, 2022 by makhdoom ghaya Rajesh Pradhan 1.6k views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments Sushant Gokhale commented Oct 29, 2016 reply Follow Share @Debashish. I didnt get you. Also, what is regularity condition? 0 votes 0 votes Sushant Gokhale commented Oct 29, 2016 reply Follow Share logn is less than n3 then why are you saying " then f(n) is polynomially greater " ? 0 votes 0 votes Sushant Gokhale commented Oct 29, 2016 reply Follow Share @Debashish. Got it why it falls under case 1. Thanks 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes For 1 the basic Master theorem can not be applied according to CLRS book but a modified corollary or a more genralised rule can be applied there Aboveallplayer answered Oct 28, 2016 Aboveallplayer comment Share Follow See all 0 reply Please log in or register to add a comment.
