Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
So, what is your question? –  Keneth Adrian 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. –  Jean-Victor Côté Mar 5 '12 at 19:20
    
Use recursion trees. Then forget the Master Theorem. –  JeffE Mar 5 '12 at 21:25

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer
    
(+1) Very powerful method indeed. –  Marko Riedel Jul 26 at 3:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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