Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor
-
05-11-2019 - |
Question
I was trying to solve the following question while reviewing master theorem.
Which of the following asymptotically grows faster.
(a) $ T(n) = 4T(n/2) + 10n $
(b) $ T(n) = 8T(n/3) + 24n^2 $
(c) $ T(n) = 16T(n/4) + 10n^2 $
(d) $ T(n) = 25T(n/5) + 20(n\log n)^{1.99} $
(e) They are all asymptotically the same
My calculation says, (a) is $\theta(n^2)$ (b) is $\theta(n^2)$ (c) is $\theta(n^2\log n)$. Now how can I evaluate (d)?
If $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor, how can I solve $T(n)$?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange