Akra-Bazzi method for $n^2/\log_2(n)$ driving function

66 Views Asked by At

I came across $T(n) = 3T(n/3)+8T(n/4)+n^2/\log_2(n)$ with driving function $f(x) = \frac{x^2}{\log_2(x)}$ in the CLRS 4th ed. textbook and am having a tough time applying the Akra-Bazzi method to it. My initial work involved finding a value $p$ for which $3(1/3)^p+8(1/4)^p = 1$ for which $p$ is approximately $1.85674$. Now using their expression to find the asymptotically tight bound $$T(n)=\Theta\!\left(n^p\left(1+\int_1^n \frac{f(x)}{x^{p+1}}dx\right)\right)= \Theta\!\left(n^p\left(1+\int_1^n \frac{x^{1-p}}{\log_2x}dx\right)\right)$$ For which I get an integral ($\int_1^n1/(x^{0.85674}\ln(x))dx$) that does not converge. Is there something incorrect to my work so far or does it simply mean this recurrence is unbounded?