I am trying to solve the following recurrence relation using master theorem:
$$T(n) = 4T\left(\frac{n}{2}\right)+ n^2+ n$$
I've been told its case 3 of master theorem, however I can't find any relevant examples after searching around where $f(n) = n^2+n$. How do I handle this?
Best Answer
The Master Theorem fits the recurrence into $$T(n) = aT(n/b) + f(n)$$ and so here $a=4, b=2, \log_b(a) = \log_2(4) = 2 = c,$ with $f(n) = \Theta(n^2) = \Theta(n^c)$, which fits the second case of the theorem for $k=0$.
Therefore, by the Master Theorem, $$T(n) = \Theta \left(n^2 \ln n\right).$$