How to solve $T(n) = 5T(\frac{n}{2}) + n^3 \log n$ using master method?

Question

I'm trying to solve the recurrence $T(n) = 5T(\frac{n}{2}) + n^3 \log n$ using master method.

$$ a = 5, b = 2 $$

$$ n^{\log_b a} = n^{\log_2 5} = n^{2.32} \in Θ(n^{2.32}) $$

How can I continue? Because $n^3 \log n$ is not $\in Θ(n^{2.32})$.

Answer 1

$$ \bbox[7px,border:2px solid red] {\text{MASTER THEOREM}}: $$ $$T(n)=aT(n/b)+f(n).$$ $$\bbox[1px,border:1px solid black] {a\ge 1,b>1,f(n)=Θ\big( n^k\cdot \log^p(n)\big)}$$ $$\text{CASE 1}:$$

$$ \text{if } \log_b(a)>k\text{ then: }\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^{\log_b(a)}\big)} $$

---

$$\text{CASE 2}:$$

$$\text{if } \log_b(a)=k:\begin{cases} \text{if $p>-1:\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^k\cdot \log^{p+1}(n)\big)}$} \\ \text{if $p=-1:\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^k\cdot \log\big( \log(n)\big)\big)} $ }\\ \text{if $p<-1:\quad \bbox[1px,border:1.5px solid black] {T(n)=Θ\big( n^k\big)}$ }\\ \end{cases} $$

---

$$\text{CASE 3}:$$

$$\text{if $\log_b(a)<k:\begin{cases} \text{if $p\ge 0:\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^k\cdot\log^p(n)\big)} $} \\ \text{if $p<0:\quad \bbox[0.5px,border:1px solid black] {T(n)=\mathcal O \big( n^k\big)} $} \end{cases}$}$$

---

Note that $a=5,b=2,\log_2(5)<k ,k=3,p=1$, hence $$T(n)=\Theta\big(n^3\cdot \log(n)\big).$$