2 votes 2 votes Solve this recurrence equation using Master's theorem T(n) = 64 T(n/8) - n 2 log n Algorithms algorithms master-theorem time-complexity + – sh!va asked Oct 29, 2016 sh!va 2.5k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Kapil commented Oct 29, 2016 reply Follow Share Master method cannot be applied, as F(N) = N2 Log N is decreasing . 0 votes 0 votes mcjoshi commented Oct 29, 2016 reply Follow Share $\tt T(n) = 64T(\frac{n}{8}) + n^2log(\frac{1}{n})$ Take on from here. 1 votes 1 votes Kapil commented Oct 29, 2016 reply Follow Share Still it falls between 1 and 2 . 1 votes 1 votes Prashant. commented Oct 29, 2016 reply Follow Share yup master theorm not apllicable. 1 votes 1 votes Kapil commented Oct 29, 2016 reply Follow Share Akra Bazzi can be easily applied :) 0 votes 0 votes LavTheRawkstar commented Feb 1, 2017 reply Follow Share Please tell how to apply Akra Bazii in the following recurrence : T(n)=T(n/2)+ T(n/4) +n2 0 votes 0 votes Shubham Sharma 2 commented Feb 1, 2017 reply Follow Share I think Answer is O(n^2). 0 votes 0 votes sumit_kumar commented Jul 3, 2017 reply Follow Share Following 2 case are possible : 1.) For worst case , recurrence relation is T(n) = 2T(n/2) + n2 {as T(n/2) is larger problem then T(n/4) } 2.) For best case , recurrence relation is T(n)= 2 T(n/4) + n2 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes As this N2logN Function is decreasing Master Theorem can not be applied here.. Aboveallplayer answered Oct 29, 2016 Aboveallplayer comment Share Follow See 1 comment See all 1 1 comment reply sumit_kumar commented Jul 3, 2017 reply Follow Share what do u mean by (N2 LOG N ) IS DECREASING ? 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes the answer will be T(n)=theta(n^2 log^2 n) Anurag Lahon answered Oct 31, 2016 Anurag Lahon comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes master theorem can't be applied Shashank Kumar Mishr answered Mar 7, 2017 Shashank Kumar Mishr comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Using Advanced master's theorem https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/ T(n) = Θ($n^{2}$loglogn) nadeshseen answered Oct 19, 2019 nadeshseen comment Share Follow See all 0 reply Please log in or register to add a comment.