# Solving the recurrence $3T(\frac{n}{4}) + n \cdot \log n$ by the Recurrence Tree method

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)

• 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.) – Did Mar 5 '17 at 7:54
• @Did Wrongly formulated in what particular way? – QPTR Mar 5 '17 at 8:16
• 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. – Did Mar 5 '17 at 8:20
• @QPTR I think you can solve it using the Akra-Bazzi theorem. – Alex Vong Mar 5 '17 at 8:22
• @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? – QPTR Mar 5 '17 at 8:32

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)$$

• 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. – QPTR Mar 31 '17 at 17:43