4.4 The recursion-tree method for solving recurrences

4.4-1

First let's create a recursion tree for the recurrence $T(n)=3T(\frac{n}{2})+n$ and assume that n is an exact power of 2.

Each level has three times more nodes than the level above, so the number of nodes at depth i is $3^i$. And each node at depth i, for $i=0,1,2,\dots ,\lg n-1$, has a cost of $\frac{n}{2^i}$. So the total cost over all nodes at depth i, is $3^i\frac{n}{2^i}=(\frac{3}{2}{)}^{i}n$. The bottom level, at depth $\lg n$, has $3^{\lg n}=n^{\lg 3}$ nodes, each contributing cost $T(1)$, for a total cost of $n^{\lg 3}T(1)$, which is $\mathrm{\Theta }(n^{\lg 3})$. So:

$$\begin{array}{rcl}T(n)& =& \sum _{i=0}^{\lg n-1}(\frac{3}{2}{)}^{i}n+\mathrm{\Theta }(n^{\lg 3})\\ & =& n\frac{1-(\frac{3}{2}{)}^{\lg n}}{1-\frac{3}{2}}+\mathrm{\Theta }(n^{\lg 3})\\ & =& 2n\frac{3^{\lg n}-2^{\lg n}}{2^{\lg n}}+\mathrm{\Theta }(n^{\lg 3})\\ & =& 2n\frac{3^{\lg n}-2^{\lg n}}{n}+\mathrm{\Theta }(n^{\lg 3})\\ & =& 2(3^{\lg n}-2^{\lg n})+\mathrm{\Theta }(n^{\lg 3})\\ & =& 2(n^{\lg 3}-n)+\mathrm{\Theta }(n^{\lg 3})\\ & <& 2n^{\lg 3}+\mathrm{\Theta }(n^{\lg 3})\\ & =& O(n^{\lg 3})\end{array}$$

Thus, we have derived a guess of $T(n)=O(n^{\lg 3})$ for our original recurrence. Now let's use the substitution method to verify that our guess was correct. We want to show that $T(n)\le c{n}^{\lg 3}$ for some constant $c>0$. So:

$$\begin{array}{rcl}T(n)& =& 3T(\lfloor \frac{n}{2}\rfloor )+n\\ & \le & 3c\lfloor \frac{n}{2}{\rfloor }^{\lg 3}+n\\ & \le & 3c(\frac{n}{2}{)}^{\lg 3}+n\\ & =& 3c(\frac{n}{2}{)}^{\lg 3}+n\\ & =& 3c\frac{n^{\lg 3}}{2^{\lg 3}}+n\\ & =& 3c\frac{n^{\lg 3}}{3}+n\\ & =& c{n}^{\lg 3}+n\end{array}$$

But $c{n}^{\lg 3}+n>c{n}^{\lg 3}$, so we need to try another guess. Let's try $T(n)\le c{n}^{\lg 3}-\frac{2n}{3}$. So:

$$\begin{array}{rcl}T(n)& =& 3T(\lfloor \frac{n}{2}\rfloor )+n\\ & \le & 3(c\lfloor \frac{n}{2}{\rfloor }^{\lg 3}-\frac{n}{3})+n\\ & \le & 3(c(\frac{n}{2}{)}^{\lg 3}-\frac{n}{3})+n\\ & =& 3c(\frac{n}{2}{)}^{\lg 3}\\ & =& c{n}^{\lg 3}\end{array}$$

4.4-2

First let's create a recursion tree for the recurrence $T(n)=T(\frac{n}{2})+n^2$ and assume that n is an exact power of 2.

The number of nodes at depth i is 1. And each node at depth i, for $i=0,1,2,\dots ,\lg n-1$, has a cost of $\frac{n^2}{4^i}$. So the total cost over all nodes at depth i, is $\frac{n^2}{4^i}$. The bottom level, at depth $\lg n$, has 1 node, which contributing cost $T(1)$, for a total cost of $T(1)$, which is $\mathrm{\Theta }(1)$. So:

$$\begin{array}{rcl}T(n)& =& \sum _{i=0}^{\lg n-1}\frac{n^2}{4^i}+\mathrm{\Theta }(1)\\ & <& \sum _{i=0}^{\mathrm{\infty }}\frac{n^2}{4^i}+\mathrm{\Theta }(1)\\ & =& \frac{1}{1-\frac{1}{4}}{n}^2+\mathrm{\Theta }(1)\\ & =& \frac{4}{3}{n}^2+\mathrm{\Theta }(1)\\ & =& O(n^2)\end{array}$$

Thus, we have derived a guess of $T(n)=O(n^2)$ for our original recurrence. Now let's use the substitution method to verify that our guess was correct. We want to show that $T(n)\le c{n}^2$ for some constant $c>0$. So:

$$\begin{array}{rcl}T(n)& =& T(\frac{n}{2})+n^2\\ & \le & c(\frac{n}{2}{)}^2+n^2\\ & =& (\frac{c}{4}+1)n^2\\ & \le & c{n}^2\end{array}$$

where the last step holds as long as $c\ge \frac{4}{3}$.

4.4-3

When n is large, the difference between $\frac{n}{2}+2$ and $\frac{n}{2}$ not that large, so it's also a sloppiness that we can tolerate. Then let's create a recursion tree for the recurrence $T(n)=4T(\frac{n}{2})+n$ and assume that n is an exact power of 2.

Each level has four times more nodes than the level above, so the number of nodes at depth i is $4^i$. And each node at depth i, for $i=0,1,2,\dots ,\lg n-1$, has a cost of $\frac{n}{2^i}$. So the total cost over all nodes at depth i, is $4^i\frac{n}{2^i}=2^{i}n$. The bottom level, at depth $\lg n$, has $4^{\lg n}=n^2$ nodes, each contributing cost $T(1)$, for a total cost of $n^{2}T(1)$, which is $\mathrm{\Theta }(n^2)$. So:

$$\begin{array}{rcl}T(n)& =& \sum _{i=0}^{\lg n-1}{2}^{i}n+\mathrm{\Theta }(n^2)\\ & =& n\frac{1-2^{\lg n}}{1-2}+\mathrm{\Theta }(n^2)\\ & =& n(n-1)+\mathrm{\Theta }(n^2)\\ & =& n^2-n+\mathrm{\Theta }(n^2)\\ & =& O(n^2)\end{array}$$

Thus, we have derived a guess of $T(n)=O(n^2)$ for our original recurrence. Now let's use the substitution method to verify that our guess was correct. We want to show that $T(n)\le c{n}^2$ for some constant $c>0$. So:

$$\begin{array}{rcl}T(n)& =& 4T(\frac{n}{2}+2)+n\\ & \le & 4c(\frac{n}{2}+2{)}^2+n\\ & =& 4c(\frac{n^2}{4}+2n+4)+n\\ & =& c{n}^2+8cn+16c+n\\ & =& c{n}^2+(8c+1)n+16c\end{array}$$

But $c{n}^2+(8c+1)n+16c>c{n}^2$, so we need to try another guess, let's try $T(n)\le c{n}^2-5n$. So:

$$\begin{array}{rcl}T(n)& =& 4T(\frac{n}{2}+2)+n\\ & \le & 4c((\frac{n}{2}+2{)}^2-5(\frac{n}{2}+2))+n\\ & =& 4c(\frac{n^2}{4}+2n+4-\frac{5n}{2}-10)+n\\ & =& 4c(\frac{n^2}{4}-\frac{n}{2}-6)+n\\ & =& c{n}^2+(1-2c)n-24c\\ & <& c{n}^2\end{array}$$

where the last step holds as long as $c\ge \frac{1}{2}$.

4.4-4

First let's create a recursion tree for the recurrence $T(n)=2T(n-1)+1$.

Each level has two times more nodes than the level above, so the number of nodes at depth i is $2^i$. And each node at depth i, for $i=0,1,2,\dots ,n-1-1$, has a cost of 1. So the total cost over all nodes at depth i, is $2^i$. The bottom level, at depth n, has $2^{n-1}$ nodes, each contributing cost $T(1)$, for a total cost of $2^{n-1}T(1)$, which is $\mathrm{\Theta }(2^n)$. So:

$$\begin{array}{rcl}T(n)& =& \sum _{i=0}^{n-1-1}{2}^i+\mathrm{\Theta }(2^n)\\ & =& \frac{1-2^{n-1}}{1-2}+\mathrm{\Theta }(2^n)\\ & =& 2^{n-1}-1+\mathrm{\Theta }(2^n)\\ & =& O(2^n)\end{array}$$

Thus, we have derived a guess of $T(n)=O(2^n)$ for our original recurrence. Now let's use the substitution method to verify that our guess was correct. We want to show that $T(n)\le c{2}^n$ for some constant $c>0$. So:

$$\begin{array}{rcl}T(n)& =& 2T(n-1)+1\\ & \le & 2c{2}^{n-1}+1\\ & =& c{2}^n+1\end{array}$$

But $c{2}^n+1>c{2}^n$, so we need to try another guess. Lets try $T(n)\le c{2}^n-1$. So:

$$\begin{array}{rcl}T(n)& =& 2T(n-1)+1\\ & \le & 2(c{2}^{n-1}-1)+1\\ & =& c{2}^n-1\\ & <& c{2}^n\end{array}$$

4.4-5

4.4-6

First let's create a recursion tree for the recurrence $T(n)=T(\frac{n}{3})+T(\frac{2n}{3})$ and assume that n is an exact power of 3.

Each level has 2 times more nodes than the level above, so the number of nodes at depth i is $2^i$. But in this question, not all leaves reach at the bottom at the same time. The left most branch reaches the bottom first. So when the left most branch reaches the bottom, we assume other nodes also reach the bottom. Then the depth of recursion tree is ${\log }_{3}n$.

The total cost over all nodes at depth i, is $cn$ and the cost at bottom is also cn So:

$$\begin{array}{rcl}T(n)& \ge & \sum _{i=0}^{{\log }_{3}n-1}cn+cn\\ & =& cn{\log }_{3}n+cn\\ & =& \frac{c}{\lg 3}n\lg n+cn\\ & =& \mathrm{\Theta }(n\lg n)\end{array}$$

But remember we've cut some branches of the recursion tree, so $T(n)=\mathrm{\Omega }(n\lg n)$.

4.4-7

When n is large, the difference between $\frac{n}{2}$ and $\lfloor \frac{n}{2}\rfloor$ not that large, so it's also a sloppiness that we can tolerate. Then let's create a recursion tree for the recurrence $T(n)=4T(\frac{n}{2})+cn$ and assume that n is an exact power of 2.

Each level has 4 times more nodes than the level above, so the number of nodes at depth i is $4^i$. And each node at depth i, for $i=0,1,2,\dots ,\lg n-1$, has a cost of $\frac{cn}{2^i}$. So the total cost over all nodes at depth i, is $4^i\frac{cn}{2^i}=c{2}^{i}n$. The bottom level, at depth $\lg n$, has $4^{\lg n}=n^2$ nodes, each contributing cost $T(1)$, for a total cost of $n^{2}T(1)$, which is $\mathrm{\Theta }(n^2)$. So:

$$\begin{array}{rcl}T(n)& =& \sum _{i=0}^{\lg n-1}c{2}^{i}n+\mathrm{\Theta }(n^2)\\ & =& cn\frac{1-2^{\lg n}}{1-2}+\mathrm{\Theta }(n^2)\\ & =& \mathrm{\Theta }(n^2)\end{array}$$

Thus, we have derived a guess of $T(n)=O(n^2)$ for our original recurrence. Now let's use the substitution method to verify that our guess was correct. We want to show that $T(n)\le d{n}^2$ for some constant $d>0$. So:

$$\begin{array}{rcl}T(n)& =& 4T(\lfloor \frac{n}{2}\rfloor )+cn\\ & \le & 4T(\frac{n}{2})+cn\\ & \le & 4d(\frac{n}{2}{)}^2+cn\\ & =& d{n}^2+cn\end{array}$$

But $d{n}^2+cn>d{n}^2$, so let's try another guess, let's try $T(n)\le d{n}^2-dn$.

$$\begin{array}{rcl}T(n)& =& 4T(\lfloor \frac{n}{2}\rfloor )+cn\\ & \le & 4T(\frac{n}{2})+cn\\ & \le & 4d((\frac{n}{2}{)}^2-\frac{n}{2})+cn\\ & =& d{n}^2+(c-2d)n\\ & \le & d{n}^2\end{array}$$

where the last step holds as long as $d\ge \frac{c}{2}$.

So $T(n)=O(n^2)$. Then we want to show that $T(n)\ge d{n}^2$ for some constant $d>0$. So:

$$\begin{array}{rcl}T(n)& =& 4T(\lfloor \frac{n}{2}\rfloor )+cn\\ & \ge & 4T(\frac{n-(2-1)}{2})+cn\\ & =& 4T(\frac{n-1}{2})+cn\\ & \ge & 4d(\frac{n-1}{2}{)}^2+cn\\ & =& d{n}^2+(c-2d)n+d\\ & >& d{n}^2\end{array}$$

where the last step holds as long as $d<\frac{c}{2}$.

So $T(n)=\mathrm{\Omega }(n^2)$, so $T(n)=\mathrm{\Theta }(n^2)$.

4.4-8

First let's create a recursion tree for the recurrence $T(n)=T(n-a)+T(a)+cn$ and assume that n - 1 is divisible by a.

The total cost over all nodes at depth i, for $i=0,1,2,\dots ,\frac{n-1}{a}-1$, is $c(n-(i-1)a),\text{ for }i\ge 1$. The bottom level, at depth $\frac{n-1}{a}$, the total cost is $T(1)+ca$, which is $\mathrm{\Theta }(a)$. So:

$$\begin{array}{rcl}T(n)& =& cn+\sum _{i=1}^{\frac{n-1}{a}-1}c(n-(i-1)a)+\mathrm{\Theta }(a)\\ & =& cn+\sum _{i=1}^{\frac{n-1}{a}-1}cn-\sum _{i=1}^{\frac{n-1}{a}-1}(i-1)ca+\mathrm{\Theta }(a)\\ & =& \frac{n-1}{a}cn-\frac{n^2-2a-3na+3a+2a^2+1}{2a}c\\ & =& \frac{n^2+3na-3a-2a^2-1}{2a}c\\ & =& \mathrm{\Theta }(n^2)\end{array}$$

Thus, we have derived a guess of $T(n)=\mathrm{\Theta }(n^2)$ for our original recurrence. Now let's use the substitution method to verify that our guess was correct. We want to show that $T(n)\le d{n}^2$ for some constant $d>0$. So:

$$\begin{array}{rcl}T(n)& =& T(n-a)+T(a)+cn\\ & \le & d(n-a{)}^2+d{a}^2+cn\\ & =& d{n}^2+(c-ad)n+(2a^2-an)d\\ & \le & d{n}^2\end{array}$$

where the last step holds as long as $d\ge \frac{c}{a}$ and $n\ge 2a$.

So $T(n)=O(n^2)$.

Then we want to show that $T(n)\ge d{n}^2$ for some constant $d>0$. So:

$$\begin{array}{rcl}T(n)& =& T(n-a)+T(a)+cn\\ & \ge & d(n-a{)}^2+d{a}^2+cn\\ & =& d{n}^2+(c-2ad)n+2a^{2}d\\ & >& d{n}^2\end{array}$$

where the last step holds as long as $d<\frac{c}{2a}$.

So $T(n)=\mathrm{\Omega }(n^2)$. So $T(n)=\mathrm{\Theta }(n^2)$.

4.4-9

First let's create a recursion tree for the recurrence $T(n)=T(\alpha n)+T((1-\alpha )n)+cn$.

So we can see not each branch reaches at the bottom at the same time, it might be the left most branch reaches at the bottom first, or the right most branch reaches at the bottom first. It depends on which is smaller, $\alpha$ or $1-\alpha$. Let $\alpha \le 1-\alpha$, so we get $\alpha \le \frac{1}{2}$. That is, when $0<\alpha \le \frac{1}{2}$, the left most branch reaches at the bottom first, when $\frac{1}{2}<\alpha <1$, the right most branch reaches at the bottom first.

If $0<\alpha \le \frac{1}{2}$, when the left most branch reaches at the bottom, let's assume other branches also reach at the bottom, so the total cost over all nodes at depth i, for $i=0,1,2,...,{\log }_{\alpha }\frac{1}{n}-1$, is cn. The cost at the bottom is also cn. So:

$$\begin{array}{rcl}T(n)& =& T(\alpha n)+T((1-\alpha )n)+cn\\ & \ge & \sum _{i=0}^{{\log }_{\alpha }\frac{1}{n}-1}cn+cn\\ & =& cn({\log }_{\alpha }\frac{1}{n})+cn\\ & =& cn\frac{\lg n}{\lg \frac{1}{\alpha }}+cn\\ & >& cn\frac{\lg n}{\lg \frac{1}{\alpha }}\\ & =& \mathrm{\Omega }(n\lg n)\end{array}$$

Thus, we have derived a guess of $T(n)=\mathrm{\Omega }(n\lg n)$ for our original recurrence. Now let's use the substitution method to verify that our guess was correct. We want to show that $T(n)\ge dn\lg n$ for some constant $d>0$. So:

$$\begin{array}{rcl}T(n)& =& T(\alpha n)+T((1-\alpha )n)+cn\\ & \ge & d\alpha n\lg (\alpha n)+d(1-\alpha )n\lg ((1-\alpha )n)+cn\\ & =& d\alpha n(\lg \alpha +n)+d(1-\alpha )n(\lg (1-\alpha )+\lg n)+cn\\ & =& dn\lg n+d\alpha \lg \alpha n+d(1-\alpha )\lg (1-\alpha )n+cn\\ & \ge & dn\lg n+d\alpha \lg \alpha n+d\alpha \lg \alpha n+cn(0<\alpha \le \frac{1}{2})\\ & =& dn\lg n+(c+2d\alpha \lg \alpha )n\\ & \ge & dn\lg n\end{array}$$

where the last step holds as long as $d\le \frac{c}{2\alpha \lg \frac{1}{\alpha }}$.

Now let's check the right most branch. When it reaches at the bottom, other branches have already reached at the bottom, if the tree depth is k, let's assume other branches become T(1) at depth k - 1.

Each level has two times more nodes than the level above, so the number of nodes at depth i is $2^i$. And total cost over all nodes at depth i, for $i=0,1,2,...,{\log }_{1-\alpha }\frac{1}{n}$, is cn. The cost at the bottom is $T(1)$. So:

$$\begin{array}{rcl}T(n)& =& T(\alpha n)+T((1-\alpha )n)+cn\\ & \le & \sum _{i=0}^{{\log }_{1-\alpha }\frac{1}{n}-1}cn+\mathrm{\Theta }(1)\\ & =& cn({\log }_{1-\alpha }\frac{1}{n})+\mathrm{\Theta }(1)\\ & =& cn\frac{\lg n}{{\lg }_{\frac{1}{1-\alpha }}}+\mathrm{\Theta }(1)\\ & <& cn\frac{\lg n}{\lg \frac{1}{1-\alpha }}+n\lg n\\ & =& O(n\lg n)\end{array}$$

Thus, we have derived a guess of $T(n)=O(n\lg n)$ for our original recurrence. Now let's use the substitution method to veify that our guess was correct. We want to show that $T(n)\le dn\lg n$ for some constant $d>0$. So:

$$\begin{array}{rcl}T(n)& =& T(\alpha n)+T((1-\alpha )n)+cn\\ & \le & d\alpha n\lg (\alpha n)+d(1-\alpha )n\lg ((1-\alpha )n)+cn\\ & =& d\alpha n(\lg \alpha +n)+d(1-\alpha )n(\lg (1-\alpha )+\lg n)+cn\\ & =& dn\lg n+d\alpha \lg \alpha n+d(1-\alpha )\lg (1-\alpha )n+cn\\ & \le & dn\lg n+d(1-\alpha )\lg (1-\alpha )n+d(1-\alpha )\lg (1-\alpha )n+cn(0<\alpha \le \frac{1}{2})\\ & =& dn\lg n+(c+2d(1-\alpha )\lg (1-\alpha ))n\\ & \le & dn\lg n\end{array}$$

where the last step holds as long as $d\ge \frac{c}{2(1-\alpha )\lg \frac{1}{1-\alpha }}$.

So we proved $T(n)=\mathrm{\Omega }(n\lg n)$ and $T(n)=O(n\lg n)$. So $T(n)=\mathrm{\Theta }(n\lg n)$ when $0<\alpha \le \frac{1}{2}$.

Then let's check another case, when $\frac{1}{2}<\alpha <1$. In this case, the right most branch reaches at the bottom first. Let's assume other branches also reach at the bottom, so the total cost over all nodes at depth i, for $i=0,1,2,...,{\log }_{1-\alpha }\frac{1}{n}$, is cn. The cost at the bottom is cn. So:

$$\begin{array}{rcl}T(n)& =& T(\alpha n)+T((1-\alpha )n)+cn\\ & \ge & \sum _{i=0}^{{\log }_{1-\alpha }\frac{1}{n}-1}cn+cn\\ & =& cn({\log }_{1-\alpha }\frac{1}{n})+cn\\ & =& cn\frac{\lg n}{{\lg }_{\frac{1}{1-\alpha }}}+cn\\ & >& cn\frac{\lg n}{{\lg }_{\frac{1}{1-\alpha }}}\\ & =& \mathrm{\Omega }(n\lg n)\end{array}$$

Thus, we have derived a guess of $T(n)=\mathrm{\Omega }(n\lg n)$ for our original recurrence. Now let's use the substitution method to verify that our guess was correct. We want to show that $T(n)\ge dn\lg n$ for some constant $d>0$. So:

$$\begin{array}{rcl}T(n)& =& T(\alpha n)+T((1-\alpha )n)+cn\\ & \ge & d\alpha n\lg (\alpha n)+d(1-\alpha )n\lg ((1-\alpha )n)+cn\\ & =& d\alpha n(\lg \alpha +n)+d(1-\alpha )n(\lg (1-\alpha )+\lg n)+cn\\ & =& dn\lg n+d\alpha \lg \alpha n+d(1-\alpha )\lg (1-\alpha )n+cn\\ & >& dn\lg n+d(1-\alpha )\lg (1-\alpha )n+d(1-\alpha )\lg (1-\alpha )n+cn(\frac{1}{2}<\alpha <1)\\ & =& dn\lg n+(c+2d(1-\alpha )\lg (1-\alpha ))n\\ & \ge & dn\lg n\end{array}$$

where the last step holds as long as $d\le \frac{c}{2(1-\alpha )\lg \frac{1}{1-\alpha }}$.

Now let's check the left most branch. When it reaches at the bottom, other branches have already reached at the bottom, if the tree depth is k, let's assume other branches become T(1) at depth k - 1.

Each level has two times more nodes than the level above, so the number of nodes at depth i is $2^i$. And total cost over all nodes at depth i, for $i=0,1,2,...,{\log }_{\alpha }\frac{1}{n}-1$, is cn. The cost at the bottom is T(1). So:

$$\begin{array}{rcl}T(n)& =& T(\alpha n)+T((1-\alpha )n)+cn\\ & <& \sum _{i=0}^{{\log }_{\alpha }\frac{1}{n}-1}cn+\mathrm{\Theta }(1)\\ & =& cn({\log }_{\alpha }\frac{1}{n})+\mathrm{\Theta }(1)\\ & =& cn\frac{\lg n}{{\lg }_{\frac{1}{\alpha }}}+\mathrm{\Theta }(1)\\ & <& cn\frac{\lg n}{\lg \frac{1}{\alpha }}+n\lg n\\ & =& O(n\lg n)\end{array}$$

Thus, we have derived a guess of $T(n)=O(n\lg n)$ for our original recurrence. Now let's use the substitution method to veify that our guess was correct. We want to show that $T(n)\le dn\lg n$ for some constant $d>0$. So:

$$\begin{array}{rcl}T(n)& =& T(\alpha n)+T((1-\alpha )n)+cn\\ & \le & d\alpha n\lg (\alpha n)+d(1-\alpha )n\lg ((1-\alpha )n)+cn\\ & =& d\alpha n(\lg \alpha +n)+d(1-\alpha )n(\lg (1-\alpha )+\lg n)+cn\\ & =& dn\lg n+d\alpha \lg \alpha n+d(1-\alpha )\lg (1-\alpha )n+cn\\ & <& dn\lg n+d\alpha \lg \alpha n+d\alpha \lg \alpha n+cn(\frac{1}{2}<\alpha <1)\\ & =& dn\lg n+(c+2d\alpha \lg \alpha )n\\ & \le & dn\lg n\end{array}$$

where the last step holds as long as $d\ge \frac{c}{2\alpha \lg \frac{1}{\alpha }}$.

So we proved $T(n)=\mathrm{\Omega }(n\lg n)$ and $T(n)=O(n\lg n)$. So $T(n)=\mathrm{\Theta }(n\lg n)$ when $\frac{1}{2}<\alpha <1$. Thus $T(n)=\mathrm{\Theta }(n\lg n)$ for all $0<\alpha <1$.