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.2k 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 Swati Rauniyar commented Sep 7, 2017 i edited by Swati Rauniyar Sep 7, 2017 reply Follow Share I tried using recurrence tree method- getting wrong answer. Please tell me where am I going wrong? 3 votes 3 votes Swati Rauniyar commented Sep 13, 2017 reply Follow Share @Downvoter, I'm asking about the mistake I did in recurrence tree method. If you can't answer my query move on and read next comments rather than downvoting mine. 5 votes 5 votes air1ankit commented Jan 18, 2018 reply Follow Share dont worry about downvote @swati, they are working for the point not knowledge.. 0 votes 0 votes sutanay3 commented Apr 14, 2018 reply Follow Share https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture3.pdf Follow page 4 for explanation. The term looks complicated but we can bound it (from above) by the sum of the infinite series. 0 votes 0 votes meghna commented Jul 17, 2018 reply Follow Share @ Swati Rauniyar in your summation, its decreasing G.P series, instead you can neglect it and you will have T= O(n) 1 votes 1 votes ankitgupta.1729 commented Oct 10, 2018 i edited by ankitgupta.1729 Jul 28, 2022 reply Follow Share @Swati , you have taken no. of terms in GP as $log_{\frac{4}{3}}n$ . It should be $log_{4}n$. Because here , size of each subproblem is decreased be 4 everytime like $n \rightarrow \frac{n}{4} \rightarrow \frac{n}{4^{2}}\rightarrow \frac{n}{4^{3}}\rightarrow ......\rightarrow \frac{n}{4^{k}}$ from level $0$ to level $k$ ..so there are total $k+1$ levels in the recursion tree. So, height of the tree will be $k+1$. It means no. of terms in our GP will also be $k+1$. Now , according to given base condition , $\frac{n}{4^{k}} = 1$ $\Rightarrow k = log_{4} n$ So, height of the tree = no. of terms in GP = $log_{4}n$. So, Total cost = $(\frac{3}{4})^{0}*n+ (\frac{3}{4})^{1}*n +(\frac{3}{4})^{2} *n +.....+ (\frac{3}{4})^{k} *n$ Now , summation of this GP will be :- $n* [\frac{1-(\frac{3}{4})^{k+1}}{1-\frac{3}{4}}] = n* [\frac{1-(\frac{3}{4})^{k}* \frac{3}{4}}{\frac{1}{4}}] = n* [\frac{1-(\frac{3}{4})^{log_{4}n}* \frac{3}{4}}{\frac{1}{4}}] = n* [\frac{1-(3)^{log_{4}n}* \frac{3}{4n}}{\frac{1}{4}}]$ $4n - 3^{log_{4}n}*3 =4n - 3^{\frac{log_{3}n}{log_{3}4}}*3 = 4n - (3^{log_{3}n})^{\frac{1}{log_{3}4}}*3 = 4n - n^{\frac{1}{log_{3}4}}*3$ Now , we can neglect negative term for large value of $n$ , So , $T(n) = O(n)$ Edit: I have not used $T(1)=2$ in the expression of Total Cost. So, here total cost will be: $n + 3 \left( \frac{n}{4} \right) + 3^2\left( \frac{n}{4^2}\right) + 3^3\left( \frac{n}{4^3} \right)+....+3^{k-1}\left(\frac{n}{4^{k-1}}\right)+ 3^k T(1)$ $\left(\frac{3}{4}\right)^0 n + \left(\frac{3}{4}\right)^1 n +\left(\frac{3}{4}\right)^2 n + \left(\frac{3}{4}\right)^3 n +....+ \left(\frac{3}{4}\right)^{k-1} n + 3^k T(1)$ $\left(\frac{3}{4}\right)^0 n + \left(\frac{3}{4}\right)^1 n +\left(\frac{3}{4}\right)^2 n + \left(\frac{3}{4}\right)^3 n +....+ \left(\frac{3}{4}\right)^{k-1} n + 3^k \times 2$ $3^k \times 2 + \left(\frac{3}{4}\right)^0 n + \left(\frac{3}{4}\right)^1 n +\left(\frac{3}{4}\right)^2 n + \left(\frac{3}{4}\right)^3 n +....+ \left(\frac{3}{4}\right)^{k-1} n $ $2\times3^k + n \left( \left(\frac{3}{4}\right)^0 + \left(\frac{3}{4}\right)^1 +\left(\frac{3}{4}\right)^2 + \left(\frac{3}{4}\right)^3 +....+ \left(\frac{3}{4}\right)^{k-1} \right)$ $2 \times 3^k + 4n (1 - \left (\frac{3}{4} \right)^k)$ $2 \times 3^{\log_4 n} + 4n \left(1 - \left (\frac{3}{4} \right)^{\log_4 n}\right)$ $2\times n^{\log_4 3} + 4n - 4n \left( \frac{3}{4}\right)^{\log_4 n}$ $2n^{\log_4 3} + 4n - 4 n^{\log_4 3}$ $4n - 2 n^{\log_4 3}$ Hence, $T(n) \sim (4n)_{n \rightarrow \infty}$ 7 votes 7 votes haider000 commented May 24, 2020 reply Follow Share you made a mistake at second last step where you use the log property to solve it gives 1/n instead of n take a look 0 votes 0 votes 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.