I am stucked at this problem:
Find the asymtotic tight bound for the following recurrences:
(Assume that $T(n)$ is constant for sufficiently small $n$)
(1) $T(n)=T(n-1)+n lg n + n$
(2) $T(n)=n^2 \sqrt{n}T(\sqrt{n})+n^5lg^3n+lg^5n$
where $lg n = \log_2n$.
It should be solved using one of the four common methods: iteration, master theorem, substitution and the Akra-Bazzi method.
For (1) I've tried several method but none worked for me.
For (2) I've divided the recurrence by $n^5$ to get the recurrence $\frac{T(n)}{n^5}=\frac{T(n^\frac{1}{2})}{(n^5)^\frac{1}{2}} + lg^3n+\frac{lg^5n}{n^5}$ then I've changed the variable $n$ to $n = 2^m$ (or $m = lg n$) and by setting $S(m)=\frac{T(2^m)}{2^{5m}}$ I got the recurrence $S(m)=S(\frac{m}{2})+m^3+\frac{m^5}{2^{5m}}$ and then I got stucked.
Thanks for any hint/help.
For the first one, note that the $n$ factor is non relevant (since $nlogn$ is asymptotically larger), and then by opening the recursion you get that $$T(n)=T(0)+\sum_{k=1}^{n}klogk $$ which you could bound by $n^2logn$ and $\frac{n^2}{4}log{\frac{n}{2}}$ for upper and lower bounds respectively, which shows that $T(n) = \Theta (n^2logn)$.
For the second one, I believe that you could imply Master's theorem (case 3) for $S(m)$ and then conclude asymptotic bound for $T(n)$.