14 votes 14 votes Which of the following functions, given by there recurrence, grows the fastest asymptotically? $T(n) = 4T\left ( \frac{n}{2} \right ) + 10n$ $T(n) = 8T\left ( \frac{n}{3} \right ) + 24n^{2}$ $T(n) = 16T\left ( \frac{n}{4} \right ) + 10n^{2}$ $T(n) = 25T\left ( \frac{n}{5} \right ) + 20\left ( n \log n \right )^{1.99}$ They all are asymptotically the same Algorithms tifr2018 asymptotic-notation recurrence-relation + – Arjun asked Dec 10, 2017 • edited May 14, 2018 by Milicevic3306 Arjun 3.6k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply mrinmoyh commented Apr 1, 2019 reply Follow Share Extended Masters theorem 1 votes 1 votes `JEET commented Dec 4, 2019 reply Follow Share This isn't the extneded master's theorem. This is simply the master's theorem. 0 votes 0 votes mrinmoyh commented Dec 5, 2019 reply Follow Share what is Extended Master's Theorem 0 votes 0 votes nishant_magarde commented Dec 16, 2019 reply Follow Share Extended Masters theorem - If a recurrence equations looks something like this- $T(n) = aT(n-b) + O(n^{k})$ then, Case 1: if $a>1$, $O(n^{k}a^{n/b})$ Case 2: if $a=1$, $O(n^{k+1})$ Case 3: if $a<1$, $O(n^k)$ 0 votes 0 votes Please log in or register to add a comment.
Best answer 16 votes 16 votes By applying master theorem, (a) T(n) = $\Theta$($n^2$) (b) T(n) = $\Theta$($n^2$) (c) T(n) = $\Theta$($n^2$*log n) (d) T(n) = $\Theta$($n^2$) C is growing fastest. Hemant Parihar answered Dec 10, 2017 • selected Dec 19, 2017 by Hemant Parihar Hemant Parihar comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments Sanjay Mahaveer commented Sep 27, 2018 reply Follow Share Thanks for explanation 0 votes 0 votes chauhansunil20th commented Dec 3, 2018 i edited by chauhansunil20th Dec 3, 2018 reply Follow Share I don't agree to @Hemant Parihar $(nlogn)^{1.99} = O(n^2)$ is not correct. Take $n=2^{256}$ $n^2 = (2^{256})^2 = 2^{512}$ $(nlogn)^{1.99} = (2^{256}*256)^{1.99} = (2^{264})^{1.99} = 2^{525}$ take any larger vale, hence $n^2=O(nlogn)^{1.99})$ in fact $n^2logn$ is also $O(nlogn)^{1.99})$ 0 votes 0 votes vishnu_m7 commented Aug 14, 2020 reply Follow Share Rather than putting values consider this : $(nlogn)^{1.99} = n^{1.99}*(logn)^{1.99}$ and $n^{2} = n^{1.99}*n^{0.01}$ We know that asymptotically $n^{0.01} > (logn)^{1.99}$ [Ref: https://en.wikipedia.org/wiki/Time_complexity] Therefore, $(nlogn)^{1.99} = O(n^2)$ 1 votes 1 votes Please log in or register to add a comment.