Master theorem: When a $f(n)$ is smaller or larger than $n^{\log_b a}$by less than a polynomial factor

cs.stackexchange https://cs.stackexchange.com/questions/110888

  •  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
scroll top