# Solving recurrences of the form $T(n)=aT(n/a)+Θ(nlgn)$

On pages 95 and 96 of the third edition of the CLRS book, we find the following, which applies here since $a=b$ is all it takes to block the application of the Master Theorem: "Although $n\lg n$ is asymptotically larger than n, it is not polynomially larger because the ratio $\tfrac{n\lg n}{n}=\lg n$ is asymptotically less than $n^{\epsilon}$ for any positive constant $\epsilon$. Consequently, the recurrence falls into the gap between case 2 and case 3." For a solution, the authors send us to exercise 4.6.2 on page 106:

"Show that if $f\left(n\right)=\Theta\left(n^{\log_{b}a}\lg^{k}n\right)$, where $k\geq0$, then the master recurrence has solution $T\left(n\right)=\Theta\left(n^{\log_{b}a}\lg^{k+1}n\right)$. For simplicity, confine your analysis to exact powers of b."

(Here $\lg^k n$ is CLRS's notation for $(\log_2 n)^k$.)

This is where I am starting to have problems...

• So, what is your question? Mar 5 '12 at 2:18
• Exercise 4.6.2 is very challenging. I might need hints in order to be able to solve it. Mar 5 '12 at 19:20
• Use recursion trees. Then forget the Master Theorem. Mar 5 '12 at 21:25

Since this question is asked frequently I will try to work out a solution for generic positive integers $a$ where $a\ge 2$.

Suppose we have $T(0)=0$ and $$T(1)=T(2)=\ldots =T(a-1)=1$$ and for $n\ge a$ $$T(n) = a T(\lfloor n/a \rfloor) + n \lfloor \log_a n \rfloor.$$

Furthermore let the base $a$ representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_a n \rfloor} d_k a^k.$$

Then we can unroll the recurrence to obtain the following exact formula for $n\ge a$ $$T(n) = a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} a^j \times (\lfloor \log_a n \rfloor - j) \times \sum_{k=j}^{\lfloor \log_a n \rfloor} d_k a^{k-j}.$$

Now to get an upper bound consider a string consisting of the digit $a-1$ to obtain $$T(n) \le a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} a^j \times (\lfloor \log_a n \rfloor - j) \times \sum_{k=j}^{\lfloor \log_a n \rfloor} (a-1) \times a^{k-j}.$$

This simplifies to $$a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} a^j \times (\lfloor \log_a n \rfloor - j) \times (a-1) \sum_{k=0}^{\lfloor \log_a n \rfloor-j} a^k$$ which is $$a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} a^j \times (\lfloor \log_a n \rfloor - j) (a^{\lfloor \log_a n \rfloor + 1 -j} -1)$$ which turns into $$a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} (\lfloor \log_a n \rfloor - j) (a^{\lfloor \log_a n \rfloor + 1} - a^j).$$ The sum produces four terms.

The first is $$\lfloor \log_a n \rfloor^2 a^{\lfloor \log_a n \rfloor + 1}.$$ The second is $$- \lfloor \log_a n \rfloor \frac{a^{\lfloor \log_a n \rfloor}-1}{a-1}.$$ The third is $$- \frac{1}{2} a^{\lfloor \log_a n \rfloor + 1} (\lfloor \log_a n \rfloor -1) \lfloor \log_a n \rfloor$$ and the fourth is $$\frac{1}{(a-1)^2} \left(a + a^{\lfloor \log_a n \rfloor} (\lfloor \log_a n \rfloor (a-1) -a)\right).$$

This bound represented by these four terms plus the leading term is actually attained and cannot be improved upon. For the asymptotics we only need the dominant term, which is $$\left(a - \frac{1}{2} a \right) \lfloor \log_a n \rfloor^2 a^{\lfloor \log_a n \rfloor} = \frac{1}{2} a \lfloor \log_a n \rfloor^2 a^{\lfloor \log_a n \rfloor}.$$

Now for the lower bound, which occurs with a one digit followed by zeroes to give $$T(n) \ge a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} a^j \times (\lfloor \log_a n \rfloor - j) \times a^{\lfloor \log_a n \rfloor-j}.$$ This simplifies to $$a^{\lfloor \log_a n \rfloor} + \sum_{j=0}^{\lfloor \log_a n \rfloor -1} (\lfloor \log_a n \rfloor - j) \times a^{\lfloor \log_a n \rfloor}$$ which is $$a^{\lfloor \log_a n \rfloor} + a^{\lfloor \log_a n \rfloor} \sum_{j=0}^{\lfloor \log_a n \rfloor -1} (\lfloor \log_a n \rfloor - j)$$ which finally produces $$a^{\lfloor \log_a n \rfloor} + a^{\lfloor \log_a n \rfloor} \sum_{j=1}^{\lfloor \log_a n \rfloor} j$$ or $$a^{\lfloor \log_a n \rfloor} + \frac{1}{2} \lfloor \log_a n \rfloor (\lfloor \log_a n \rfloor +1) a^{\lfloor \log_a n \rfloor}.$$ The dominant term here is $$\frac{1}{2} \lfloor \log_a n \rfloor^2 a^{\lfloor \log_a n \rfloor}.$$

Joining the dominant terms of the upper and the lower bound we obtain the asymptotics $$\color{#00A}{\lfloor \log_a n \rfloor^2 \times a^{\lfloor \log_a n \rfloor} \in \Theta\left((\log_a n)^2 \times a^{\log_a n}\right) = \Theta\left((\log n)^2 \times n\right)}.$$

This MSE link has a series of similar calculations.

This is amenable to analysis by the Akra-Bazzi method. The calculations go like this, using the notation of the Wikipedia article:

\begin{eqnarray*} k & = & 1 \\ a_1 & = & a \\ b_1 & = & 1/a \\ g(x) & = & x \log x \\ h(x) & = & 0 \\ p & = & 1 \Leftarrow a_1 b_1=1 \\ T(x) & = & \Theta \left ( x \left ( 1 + \int_1^x \frac{u \log u}{u^{p+1}} du \right ) \right ) \\ & = & \Theta \left ( x \left ( 1 + \Theta \left (\log(x)^2 \right ) \right ) \right ) \\ & = & \Theta \left ( x \log(x)^2 \right ) \end{eqnarray*} This may not help you that much, as you may not be able to prove that the Akra-Bazzi method works.