1 votes 1 votes which of the following cannot be solved using masters theorem? a) T(n) = 2T(n/2) + n/logn b) T(n) = 2T(n/2) + logn c)T(n)=T(n/2)+logn d) non of these Algorithms made-easy-test-series recurrence-relation master-theorem + – manvi_agarwal asked Aug 11, 2018 edited Mar 14, 2019 by adeebafatima1 manvi_agarwal 2.1k views answer comment Share Follow See all 14 Comments See all 14 14 Comments reply Show 11 previous comments manvi_agarwal commented Aug 13, 2018 reply Follow Share b is the answer 0 votes 0 votes Shaik Masthan commented Aug 13, 2018 reply Follow Share @manvi_agarwal, answer may be wrong refer the 2nd link which i provided 0 votes 0 votes Verma Ashish commented Aug 14, 2018 reply Follow Share Sir u think by advanced master's theorem we can do all of them. Am i right?? 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes General form of master's theorem - T(n)=aT(n/b)+Q(n^k (log^p)n) where a>=1,b>1,k>=0 and p is real. according to this all are satisfied so ans is D. sandeep singh gaur answered Aug 16, 2018 sandeep singh gaur comment Share Follow See all 2 Comments See all 2 2 Comments reply Verma Ashish commented Aug 17, 2018 reply Follow Share You are right bro.. But what about this https://gateoverflow.in/227814/introduction-to-algorithms 0 votes 0 votes amcodes18 commented Jun 28, 2020 reply Follow Share Did u find answer to that? 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes Inadmissible equations The following equations cannot be solved using the master theorem: a is not a constant; the number of subproblems should be fixed non-polynomial difference between f(n) and (see below; extended version applies) cannot have less than one sub problem f(n), which is the combination time, is not positive case 3 but regularity violation. In the second inadmissible example above, the difference between and can be expressed with the ratio . It is clear that for any constant . Therefore, the difference is not polynomial and the basic form of the Master Theorem does not apply. The extended form (case 2b) does apply, giving the solution . I have completely copied this portion from wikipedia https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms). and from the second inadmissible equation, it is clear that the correct answer is A Abhilash Behera answered Jan 19, 2021 Abhilash Behera comment Share Follow See all 0 reply Please log in or register to add a comment.