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...

  • $\begingroup$ So, what is your question? $\endgroup$ Mar 5 '12 at 2:18
  • $\begingroup$ Exercise 4.6.2 is very challenging. I might need hints in order to be able to solve it. $\endgroup$ Mar 5 '12 at 19:20
  • $\begingroup$ Use recursion trees. Then forget the Master Theorem. $\endgroup$
    – JeffE
    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.


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.