23 votes 23 votes The recurrence relation $T(1) = 2$ $T(n) = 3T (\frac{n}{4}) +n$ has the solution $T(n)$ equal to $O(n)$ $O (\log n)$ $O\left(n^\frac{3}{4}\right)$ None of the above Algorithms gate1996 algorithms recurrence-relation normal + – Kathleen asked Oct 9, 2014 edited Nov 7, 2017 by kenzou Kathleen 7.1k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 23 votes 23 votes Answer: A According to Master theorem, $T(n) = aT(\frac{n}{b}) + f(n)$ can be expressed as: $T(n) = [n^{\log_ba}][T(1) + u(n)]$ where $u(n) = \Theta(h(n))$ where $h(n) = \frac{f(n)}{n^{\log_ba}} = \frac{n}{n^{\log_43}} = n^{1-\log_43}$ as $h(n) = n^r$ where $r>0$. So, $T(n) = [n^{\log_ba}][T(1) + u(n)] = T(n) = [n^{\log_43}][T(1) + \Theta(n^{1-\log_43})] = \Theta(n^{1})$. Rajarshi Sarkar answered Jun 3, 2015 edited Nov 7, 2017 by kenzou Rajarshi Sarkar comment Share Follow See all 0 reply Please log in or register to add a comment.
34 votes 34 votes Using Extended Master Theorem $T(n)=3T(\frac{n}{4})+n^{1} \log^{0} n$ $a=3 , b =4 , k=1 , p=0$ case 3 : $a<b^{k}$ is true case 3.a follows as $p=0$ Hence $T(n)$ is $\Theta (n^{1} \log^{0} ) \Rightarrow \Theta (n )$ pC answered Dec 30, 2016 pC comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments Verma Ashish commented Aug 21, 2018 reply Follow Share Yes dude 1 votes 1 votes vishalshrm539 commented Jan 20, 2019 reply Follow Share @vupadhayayx86 Anything raised to the power 0 is 1. 1 votes 1 votes palashbehra5 commented Aug 12, 2021 reply Follow Share @vishalshrm539 not 0 tho 1 votes 1 votes Please log in or register to add a comment.
20 votes 20 votes Master theorem: $n^{\log_4 3} < n$, so it is $O(n)$. Bhagirathi answered Oct 16, 2014 edited Jun 3, 2015 by Rajarshi Sarkar Bhagirathi comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments svas7246 commented Feb 17, 2021 reply Follow Share @haider000 3T(n/4) is different from T(3n/4) 0 votes 0 votes haider000 commented Feb 17, 2021 reply Follow Share thanks, @svas7246 for mentioning, I really did not pay the attention and miss read the question, will correct it. 0 votes 0 votes Rusty_01 commented Apr 28, 2022 reply Follow Share You have calculated depth of the tree wrong. It should be like this – depth of the tree getting reduced by n/4 at each level . And let’s say that at k th level size of our problem will hit 1 means T(1). then n/4^k = 1 and k = log n (base4) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes can directly use extended masters theorm as here a < b^k so t(n)=O(n^k log^p) [:- k=1,p=0] t(n)=O(n) ashwani kumar sharma answered Aug 8, 2018 ashwani kumar sharma comment Share Follow See all 0 reply Please log in or register to add a comment.