I had my final exam today in an advanced algorithms course. In it there were two recurrence relations and I used the Akra-Bazzi theorem to solve them. After the examination I was discussing the problem with one of my colleagues and they apparently got a different bound using Master theorem. My question is which of this two bounds are tighter?
The recurrences were:
$1)\quad T(n) = 8T\left(\frac{(2n-1)}{4}\right)+n^3+n\log n$
$2)\quad T(n) = 3T(n/2)+n\log^2 n $
Now, correct me if I'm wrong but Akra-Bazzi gives 1) as $\Theta(n^3\log n )$ and 2) as $\Theta(n\log^2 n )$ Can somebody please verify 2) by Akra-Bazzi? I checked and regularilty condition doesn't hold for 2) .