0
$\begingroup$

I am trying to solve the recurrence $3T\left(\frac{n}{4}\right) + n \cdot \log n$ by using the Recurrence Tree method. I've solved it until here:

$= 3 \cdot \frac{n}{4} \log \frac{n}{4}$

$= 3 \cdot 3 \cdot \frac{n}{16} \log \frac{n}{16}$

$= \sum_{i=0}^{log_4(n) + 1} \frac{3^i}{4^i} \cdot n \log(\frac{n}{4^i})$

$= n \sum_{i=0}^{log_4(n) + 1} \frac{3^i}{4^i} \left[\log(n) - log_4(4^i)\right]$

$= n\log{n} \sum_{i=0}^{\log_4(n) + 1} \frac{3^i}{4^i} - n \sum_{i=0}^{\log_4(n)} \frac{3^i}{4^i} i$

But after this I do not know how to handle the second part of the equation after subtraction. In particular, if I take the sum until infinity of the above expression, then the sum of the $i$ term in the above part would sum to infinity.

Could anyone please help me regarding this? Am I making some kind of a mistake? The final recurrence should solve to $n \log n$ (as verified by the Master's Thereom method)

$\endgroup$
  • $\begingroup$ It seems your misconception is to believe that the series $$\sum \frac{3^i}{4^i}i$$ diverges. Actually it converges hence the last RHS in your post is indeed $\Theta(n\log n)$. (As an aside, note that the formulation of your question is one of the worst I have seen recently on this site.) $\endgroup$ – Did Mar 5 '17 at 7:54
  • $\begingroup$ @Did Wrongly formulated in what particular way? $\endgroup$ – QPTR Mar 5 '17 at 8:16
  • 1
    $\begingroup$ Tons of ways. The first one: there is no recurrence in your title. Second one: the title confuses $n$ and $N$. Third one: the body repeats the faults of the title then turns to an "equation" with no LHS. And so on. $\endgroup$ – Did Mar 5 '17 at 8:20
  • $\begingroup$ @QPTR I think you can solve it using the Akra-Bazzi theorem. $\endgroup$ – Alex Vong Mar 5 '17 at 8:22
  • $\begingroup$ @Did My bad, partially corrected it. I am not sure how best to represent the treeness of the recurrence tree while solving it, so yeah, thats a bit wrong technically. Would you explain the convergence part a bit more? $\endgroup$ – QPTR Mar 5 '17 at 8:32
1
$\begingroup$

There are at least two methods to solve this problem.

We first present the Akra-Bazzi theorem:

If the recurrence is of the form $$T(x) = g(x) + \sum_{i = 1}^{k} a_i T(b_i x + h_i(x))$$ for all $x > x_0$ with the following conditions

  1. sufficient base cases
  2. $a_i > 0$ and $0 < b_i < 1$
  3. $|g(x)| \in O(x^c)$
  4. $|h_i(x)| \in O\left(\frac{x}{(\log x)^2}\right)$

Then $$T \in \Theta\left(x^p \left(1 + \int_{1}^{x} \frac{g(u)}{u^{p + 1}}\right)\right)$$ where $p$ is the solution to the equation $$\sum_{i = 1}^{k} a_i b_i^p = 1$$.

Solution 0:

We simply apply the theorem.

Note $k = 1$, $g(x) = x \log x$, $a_1 = 1$, $b_1 = \frac{1}{4}$ and $h_1(x) = 0$.

Clearly they satisfy the assumptions, so we now solve the equation $$\sum_{i = 1}^{1} a_i b_i^p = 1$$ $$\iff a_1 b_1^p = 1$$ $$\iff \left(\frac{1}{4}\right)^p = 1$$ $$\iff p = 0$$ Now proceed to solve the integral $$\int_{1}^{x} \frac{u \log u}{u^{0 + 1}} = \int_{1}^{x} \log u = [u \log u - u]_1^x = x \log x - x + 1$$ So we have $$T \in \Theta(x^0 (1 + x \log x - x + 1)) = \Theta(x \log x)$$

Solution 1:

Our plan is to express the recurrence in the form of sum, bound it by integrals and hope that the lower bound is $\Theta(n \log n)$ while the upper bound is $O(n \log n)$.

First, we put $n = 4^k$ and obtain $$T(4^k) = 3^1 T(4^{k - 1}) + 3^0 4^k \log 4^k$$ $$= 3^2 T(4^{k - 2}) + 3^1 4^{k - 1} \log 4^{k - 1} + 3^0 4^k \log 4^k$$ $$= 3^3 T(4^{k - 3}) + 3^2 4^{k - 2} \log 4^{k - 2} + 3^1 4^{k - 1} \log 4^{k - 1} + 3^0 4^k \log 4^k$$ $$\vdots$$ $$= 3^k 4^0 T(1) + 3^{k - 1} 4^1 \log 4^1 + 3^{k - 2} 4^2 \log 4^2 + \dots + 3^1 4^{k - 1} \log 4^{k - 1} + 3^0 4^k \log 4^k$$ $$= 3^k \left(T(1) + \sum_{j = 1}^{k} \left(\frac{4}{3}\right)^j \log 4^j \right)$$ $$= 3^k \left(T(1) + \log 4 \sum_{j = 1}^{k} j \left(\frac{4}{3}\right)^j\right)$$ Now we can bound the sum by integrals since the function is monotone increasing $$\int_{0}^{k} x \left(\frac{4}{3}\right)^x \le \sum_{j = 1}^{k} j \left(\frac{4}{3}\right)^j \le \int_{1}^{k + 1} x \left(\frac{4}{3}\right)^x$$ Put $a = \frac{4}{3}$

Note $$x a^x = x e^{x \log a}$$ Next we evaluate the integral using integration by parts $$\int x a^x = \int x e^{x \log a} = \frac{1}{\log a} \left(x e^{x \log a} - \int e^{x \log a}\right)$$ $$= \frac{1}{\log a} \left(x e^{x \log a} - \frac{1}{\log a} e^{x \log a}\right) + C = \frac{a^x}{\log a} \left(x - \frac{1}{\log a} \right) + C$$ So $$\int_{0}^{k} x \left(\frac{4}{3}\right)^x = \left[\frac{a^x}{\log a} \left(x - \frac{1}{\log a} \right) \right]_{0}^{k} = \frac{a^k}{\log a} \left(k - \frac{1}{\log a} \right) + \frac{1}{(\log a)^2} \in \Omega(k a^k)$$ and $$\int_{1}^{k + 1} x \left(\frac{4}{3}\right)^x = \left[\frac{a^x}{\log a} \left(x - \frac{1}{\log a} \right) \right]_{1}^{k + 1} = \frac{a^{k + 1}}{\log a} \left(k + 1 - \frac{1}{\log a} \right) - \frac{a}{\log a} \left(1 - \frac{1}{\log a} \right) \in O(k a^k)$$ So one concludes $$\sum_{j = 1}^{k} j \left(\frac{4}{3}\right)^j \in \Theta(k a^k)$$ Finally, assuming $T(1) \in \Theta(1)$, one has $$T(n) = 3^k \left(T(1) + \log 4 \sum_{j = 1}^{k} j \left(\frac{4}{3}\right)^j\right)$$ $$\in \Theta(3^k) \Theta(k a^k) = \Theta \left(3^k k \left(\frac{4}{3}\right)^k\right) = \Theta(k 4^k) = \Theta(n \log_4 n) = \Theta(n \log n)$$

$\endgroup$
  • $\begingroup$ Thanks so much for the answer, I apologize for the delay, I'll definitely accept your answer, just need to understand the Akra-Bazzi theorem a bit better. $\endgroup$ – QPTR Mar 31 '17 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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