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))$ ?
 A: 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)$$
A: Do the substitution:
$$\begin{array} {rcl}
T(n) &=& n^3\log(n) \\
     &+& 5(n/2)^3\log(n/2)\\
     &+& 5^2(n/2^2)^3\log(n/2^2)\\
     &+& 5^3(n/2^3)^3\log(n/2^3)\\
     &+& \dots \\
\\
&=& n^3\log(n) \\
     &+& 5/2^3 n^3 (\log n - \log 2)\\
     &+& 5^2/2^6 n^3 (\log n - 2\log 2)\\
     &+& 5^3/2^9 n^3 (\log n - 3 \log 2)\\
     &+& \dots \\
\\
&=& n^3\log(n) (1 + 5/2^3 + 5^2/2^6 + 5^3/2^9 + \dots) \\
&-& n^3\log(2) (0 + 1\cdot 5/2^3 + 2\cdot 5^2/2^6 + 3 \cdot 5^3/2^9 + \dots )\\
\end{array}$$
That's a geometrics series and an arithmetico-geometric series.  But you don't actually need to calculate them to get the asymptotic behavior, since it is just going to be some positive constants.
