1
$\begingroup$

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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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*} $$

$\endgroup$
1
  • $\begingroup$ I had never seen something like that. That was perfect! Thanks. $\endgroup$ Nov 14, 2023 at 4:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.