6
$\begingroup$

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

  • 0
    Use [recursion trees](http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/notes/99-recurrences.pdf). Then forget the Master Theorem.2012-03-05

2 Answers 2

4

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.

2

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.