Search code examples
algorithmmaster-theorem

How to solve this recursion T(n) = 5T(n/2) + n^2 lg n using master's theorem?


Problem 1.8 in MIT handout is the above recursion http://courses.csail.mit.edu/6.046/spring02/handouts/mastersol.pdf

Solution in the handout is T(n) = Θ(n^lg5) (case 1). I don't get any epsilon value which will satisfy the condition for case 1. Please help me out to solve this.


Solution

  • lg n is O(n^0.1) (any positive real will do instead of 0.1), so n^2 lg n is O(n^2.1), which suffices since 2.1 < lg 5 (2.32...).