How to solve the recurrence $()=5(/2)+^3()$ using iteration method How do we solve the recurrence $()=5(/2)+^3()$ using the Iteration method?
I solved the recurrence using a master method - master method
Now using the iteration method
$()=5(/2)+3() = 5(5T(/4)+(n/2)^3)*log(n/2))+n^3*logn$ $=$ ... $= 5^i(n/2^i)+n^3*log(n) * ∑(n^3*(5^k) *log(n/2^k) ) / 8^k) $
How is it equal to $Θ(n^3log(n))$ ?

Let $u_k:=T(2^k)$. Then substituting $n=2^k$ in the given equation, $$u_k=5u_{k-1}+8^kk$$
This can be solved in the usual way, $$u_k=\tfrac{1}{3} 8^{k+1} (k-\tfrac{5}{3}) + C5^k$$ Substituting $k=\log_2n$, $5^k=5^{\log_2n}=n^{\log_25}$, $$T(n)=\tfrac{8}{3}n^3(\log_2 n-\tfrac{5}{3})+Cn^{\log_2 5}=O(n^3\log_2 n)$$
