edited by
1,186 views
0 votes
0 votes

Which of the following functions given by their recurrences grows the fastest asymptotically?

  1. $T(n) = 8T(n/4) + 100n^2$
  2. $T(n) = 81T(n/9) + 10n^2$
  3. $T(n) = 16T(n/4)+ 100(n \log n)^{1.99}$
  4. $T(n) = 100T(n/100)+ n \log^2 n$

 

edited by

1 Answer

Best answer
3 votes
3 votes

A function $f$ is asymptotically larger than function $g$ means for large values (all numbers greater than some finite number) $f(n) > g(n).$

$T(n) = 81T\left( \dfrac{n}{9} \right) + 10n^2$ -- This recurrence will asymptotically grow faster than all the other options given.


By applying Master's Theorem'

  1.  $T(n) = 8T \left( \dfrac{n}{4} \right) + 100n^2$
    Recursion part, $n^{\log_b a} = n^{\log_4 8}$ and $f(n) = 100 n^2.$ Since, $f(n)$ is polynomially (by a factor of some $n^{\epsilon}, \epsilon > 0)$larger, and $f(n)$ is regular, as per Master Theorem Case 3,  $$T(n) = \Theta(f(n))= \Theta(n^2)$$
  2.  $T(n) = 81T \left( \dfrac{n}{9} \right) + 10n^2 \\ \therefore T(n) = O(n^2\log n)$
    Recursion part, $n^{\log_b a} = n^{\log_9 81} = n^2$ and $f(n) = 10 n^2.$ Since, $f(n) = \Theta (n^{\log_b a}),$ as per Master Theorem Case 2,  $$T(n) = \Theta(f(n) \log n)= \Theta(n^2 \log n)$$
  3.  $T(n) = 16T \left( \dfrac{n}{4} \right) + 100(n\log n)^{1.99}$
    Recursion part, $n^{\log_b a} = n^{\log_4 16} = n^2$ and $f(n) = 100 (n \log n)^{1.99}.$ Since, $f(n)$ is polynomially (by a factor of some $n^{\epsilon}, \epsilon > 0)$ smaller, as per Master Theorem Case 1,  $$T(n) = \Theta(n^{\log_b a})= \Theta(n^2)$$
  4.  $T(n) = 100T \left( \dfrac{n}{100} \right) + n\log^2n$
    Recursion part, $n^{\log_b a} = n^{\log_{100} 100} = n$ and $f(n) = n \log^2 n .$ Here $f(n)$ and $n^{\log_b a}$ are not asymptotically equal and they dont have a polynomial difference. (Any polynomial in $n$ is asymptotically larger than any polynomial in $\log n).$ So Master Theorem cannot be applied as such. But we can apply the Extended Master Theorem Case 2, which states that $$\text{if}\; f(n) = \Theta(n^{\log_b a} \log^k n), k > -1, \text{ then }T(n) = \Theta(n^{\log_b a} \log ^{k+1} n)$$
    Here, $k = 2.$ So, we get $$T(n) = \Theta(n \log^3 n)$$

Reference: Master Theorem

selected by
Answer:

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
1 answer
2
3 votes
3 votes
1 answer
3
mcjoshi asked Aug 30, 2016
1,524 views
Which of the following set is empty?$o (g(n)) \cap \omega (g(n))$$O (g(n)) \cap \Omega (g(n))$$o (g(n)) \cap O( g(n))$$\omega (g(n)) \cap \Omega (g(n))$
0 votes
0 votes
1 answer
4
Magma asked Dec 27, 2018
600 views
…………………………..