Solve a recurrence using Akra-Bazzi method where $p$ is not integer and integration is not easy

Question

I recently faced this problem in CLRS ed.4 and couldn't find out how to attack it and solve it. Here's the recurrence: $$T(n)=3T(\frac{n}{3})+8T(\frac{n}{4})+\frac{n^2}{\log{n}}$$

Here's what I tried: $$\frac{3}{3^p}+\frac{8}{4^p}=1$$ For $p=1$, we get $\frac{3}{3}+\frac{8}{4}>1$ and for $p=2$, we get $\frac{3}{3^2}+\frac{8}{4^2}<1$. So we conclude that $1<p<2$. Using numerical methods, we get $p\approx1.85674$. Then we can write: $$T(n)=\Theta\left(n^p(1+\int_1^n{\frac{x^2}{x^{p+1}\log{x}}}\,\mathrm{d}x)\right)=\Theta\left(n^p+n^p\int_1^n{\frac{1}{x^{p-1}\log{x}}}\,\mathrm{d}x\right)$$

Here's where I'm stuck. I know $1<p<2$ but I can't figure out or guess the intergral answer. I suspect we don't need to calculate the integral actually, but then how can we solve the recurrence then?

Any hint or help is so much appreciated!

Answer 1

The integral is in $\Theta(\frac{n^{2-p}}{\log n})$ and, substituing it back in the Akra-Bazzi formula, you get $T(n) = \Theta(n^p \cdot \frac{n^{2-p}}{\log n}) = \Theta(\frac{n^2}{\log n})$.

For the lower bound you can use: $$ \int_{2}^n \frac{1}{x^{p-1} \log x} \text{d}x \ge \int_{2}^n \frac{1}{x^{p-1} \log n} \text{d}x = \frac{1}{\log n}\int_{2}^n x^{1-p} \text{d}x = \Omega(\frac{n^{2-p}}{\log n}). $$

For the upper bound, let $t = \frac{n}{\log^{1/(2-p)} n}$ and notice that $\log t = \log n - o(\log n) = \Theta(\log n)$. Then: $$ \begin{align*} \int_{2}^n \frac{1}{x^{p-1} \log x} \text{d}x &= \int_{2}^{t} \frac{1}{x^{p-1} \log x} \text{d}x + \int_{t}^n \frac{1}{x^{p-1} \log x} \text{d}x \\ &\le \int_{2}^{t} x^{1-p} \text{d}x + \frac{1}{\log t} \int_{t}^n x^{1-p} \text{d}x \\ &= O(t^{2-p}) + O(\frac{n^{2-p}}{\log t}) \\ & =O(\frac{n^{2-p}}{\log n}) + O(\frac{n^{2-p}}{\log n}) = O(\frac{n^{2-p}}{\log n}). \end{align*} $$