3 votes 3 votes What is the solution for the recurrence $T(n)=3T(n/4)+logn$ Algorithms recurrence-relation + – Manu Madhavan asked Aug 27, 2016 Manu Madhavan 438 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply mcjoshi commented Oct 10, 2016 reply Follow Share $ \theta(n^{log_{4}(3)})$ 2 votes 2 votes PEKKA commented Dec 6, 2016 reply Follow Share What is the limiting condition ? 0 votes 0 votes mcjoshi commented Dec 9, 2016 reply Follow Share You can assume $\tt T(0) = 1$ (or) $\tt T(0) = 0$ or $\tt T(1) = 0 \;or\; 1$. Answer doesn't change 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes It will be ⊜(nlog4(3)). Rajesh Raj answered Oct 10, 2016 • selected Jan 4, 2017 by focus _GATE Rajesh Raj comment Share Follow See 1 comment See all 1 1 comment reply Sushant Gokhale commented Nov 7, 2016 reply Follow Share @Rajesh. Could you tell me which case of master theorem? I think it wont fit in first case because how do you compare n$log$43 with logn because they arent polynomially comparable, right? Plz give me detailed explanation 0 votes 0 votes Please log in or register to add a comment.
