7 votes 7 votes T(n)=4T(n/2)+n/logn this can be solved by master theorem but why t(n)=2t(n/2)+n/logn can't be solved by master theorem ? Algorithms algorithms recurrence-relation master-theorem descriptive + – vkm07 asked Jul 27, 2016 • retagged Jun 23, 2022 by Lakshman Bhaiya vkm07 4.9k views answer comment Share Follow See 1 comment See all 1 1 comment reply vijju532 commented Jun 19, 2018 reply Follow Share Caption 0 votes 0 votes Please log in or register to add a comment.
6 votes 6 votes T(n)=4T(n/2)+n/logn here nlog24 = n2 > n/logn ( i.e. not log n time big). T(n)=2T(n/2)+n/logn here nlog22 = n > n/logn ( i.e. log n time big). which is not the case of master thoerm but done by extented master theorm. Prashant. answered Jul 27, 2016 Prashant. comment Share Follow See all 4 Comments See all 4 4 Comments reply cse23 commented Jul 27, 2016 reply Follow Share but a/c to extended master theoram so answer is coming as O(n2) ..ryt? 2 votes 2 votes Sushant Gokhale commented Aug 28, 2016 reply Follow Share @cse23. Yes, but precisely theta(n^2). 0 votes 0 votes Lakshman Bhaiya commented Oct 30, 2018 reply Follow Share for $T(n)=4T(n/2)+n/logn$ $T(n)=\theta(n^{2})$ and for $T(n)=2T(n/2)+n/logn$ $T(n)=\theta(loglogn)=\theta(log^{2}n)$ 0 votes 0 votes Kaluti commented Dec 6, 2019 reply Follow Share it should be theta(n*loglogn) for 2T(n/2) +n/logn 2 votes 2 votes Please log in or register to add a comment.