let $T(n) = 2T(\frac{n}{4})+\sqrt{n}\log n$
prove with induction that $T(n) = \Theta(\sqrt{n}\log^2 n)$
I was able to prove the O part of the proof but I'm stuck with the Ω proof, while c is some const great than 0 I get the term:
$T(n) > \sqrt{n}*(c(\log^2(n)-4\log(n)+4)+\log(n))$
but from here I wasn't able to continue with reduce the term.
$T(n) = 2 T(n/4) + \sqrt{n} \log n \\ = 2^2 T(n/4^2) + \sqrt{n} (\log n + \log (n/4)) \\ = 2^3 T(n/4^3) + \sqrt{n}(\log n + \log (n/4) + \log (n/4^2))$
Thus, via induction you have
$T(n) = 2^{log_4{n}} T(1) + \sqrt{n} \displaystyle \sum_{k=0}^{\log_4 n} \log \left(\frac{n}{4^k}\right) \\ = c \sqrt{n} + \sqrt{n} \left(\log n \left(\frac{1}{2}\log n+1\right) - \frac{1}{2} \log n \left(\frac{1}{2} \log n + 1\right)\right) = c\sqrt{n} + \sqrt{n} \left( \frac{1}{4} \log^2 n + \frac{1}{2} \log n \right) $
$T(n) = \Theta(\sqrt{n} \log^2 n)$