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 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.