Assume we have this recurrence: $$T(n)=2T(\dfrac{n}{2})+\dfrac{8}{9}T(\dfrac{3n}{4})+\Theta(\dfrac{n^2}{\log{n}})$$ We want to solve it using Akra-Bazzi method. As we know, $\sum_{i=1}^k\dfrac{a_i}{b_i^p}=1$. So $\dfrac{2}{2^p}+\dfrac{\dfrac{8}{9}}{(\dfrac{4}{3})^p}=1$ and we get $p=2$. We know: $$T(n)=\Theta\left(n^p(1+\int_1^n{\dfrac{f(x)}{x^{p+1}}\text{d}x})\right)$$ Which $f(x)$ is the cost of dividing and merging of the problem. Here, $f(x)=\Theta(\dfrac{n^2}{\log{n}})$. Using Akra-Bazzi method, integrations part converts to: $\log{\log{x}}|_1^n$. But for $x=1$ the integral is divergent. So, how can I deal with these kinds of problem that integral goes to infinity?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It is sufficient for the lower limit of integration to be large enough (see the original paper).
If you pick any $n_1 > 1$, $\log \log n_1$ exists and is just some constant. Then $$\int_{n_1}^n \frac{1}{x \log x} \text{d}x = \log \log n - \log \log n_1 = \Theta(\log \log n),$$ and the solution of the recurrence is $\Theta(n^2 \log \log n)$. For convenience you can pick $n_1 = e$.
Alternatively, you can rewrite your recurrence replacing $f(n)=\frac{n^2}{\log n}$ with some function $g(n) = \Theta(f(n))$ that yields an integrand that is defined over the domain of integration. E.g., $g(n) = \frac{(2n)^2}{\log 2n}$ results in the integral $$ \begin{align*} \int_{1}^n \frac{4x^2}{x^3 \log 2x} \text{d}x&= \int_{1}^n \frac{4}{x \log 2x} \text{d}x = \int_{2}^{2n} \frac{4}{t \log t} \text{d}t = \left. 4 \log \log 2t\right|_{t=2}^{2n} \\ &= 4 \log \log 2n - 4 \log \log 2 = \Theta(\log \log n). \end{align*} $$
