8.1 Lower bounds for sorting

8.1-1

It's $\Theta(n)$, when the array is already sorted.

8.1-2

By A.11 we have $\int_0^n \lg{k} dk \leq \sum_{k = 1}^n \lg{k} \leq \int_1^{n + 1} \lg{k} dk$.

And $\int \lg{k} dk = k\lg{k} - \frac{1}{\ln2}k + c = k\lg{k} - k\lg{e} + c$, but k could not be 0, so we cannot calculate the left part. Notice that when k = 1, $\lg{k} = 0$, so $\sum_{k = 1}^n \lg{k} = \sum_{k = 2}^n \lg{k}$ for $n \geq 2$. Thus we have $\int_1^n \lg{k} dk \leq \sum_{k = 2}^n \lg{k} \leq \int_2^{n + 1} \lg{k} dk$.

For the left part:

$$ \begin{eqnarray} \int_1^n \lg{k} dk &=& n\lg{n} - n\lg{e} + c - (1\lg1 - 1\lg{e} + c) \\ &=& n(\lg{n} - \lg{e}) + \lg{e} \\ &\geq& n(\lg{n} - \frac{1}{2}\lg{n}) + \lg{e} \quad (\text{when } n \geq e^2) \\ &=& \frac{1}{2}n\lg{n} + \lg{e} \\ &>& \frac{1}{2}n\lg{n} \\ &=& \Omega(n\lg{n}) \end{eqnarray} $$

For the right part:

$$ \begin{eqnarray} \int_2^{n + 1} \lg{k} dk &=& (n + 1)\lg{(n + 1)} - (n + 1)\lg{e} + c - (2\lg2 - 2\lg{e} + c) \\ &=& (n + 1)\lg{\frac{n + 1}{e}} + 2(\lg{e} - 1) \\ &\leq& (n + 1)\lg{\frac{n + 1}{e}} + (n + 1)\lg{e} \quad (\text{when } n \geq 1 - \frac{1}{\lg{e}}) \\ &=& (n + 1)\lg{(n + 1)} \\ &<& 2n\lg{n^2} \quad (\text{when } n \geq 2) \\ &=& 4n\lg{n} \\ &=&O(n\lg{n}) \end{eqnarray} $$

So $\lg{(n!)} = \Theta(n\lg{n})$.

8.1-3

In the proof of theorem 8.1 we know that given m permutations, we have $m \leq l$, where l is the number of reachable leaves, and since a binary tree of height h has no more than $2^h$ leaves, we have $m \leq l \leq 2^h$, so $h \geq \lg{m}$.

When $m = \frac{n!}{2}$, $\lg{m} = \lg{\frac{n!}{2}} = \lg{(n!)} - 1 = \Omega(n\lg{n})$.

When $m = \frac{n!}{n}$, $\lg{m} = \lg{\frac{n!}{n}} = \lg{(n!)} - \lg{n} = \Omega(n\lg{n})$.

When $m = \frac{n!}{2^n}$, $\lg{m} = \lg{\frac{n!}{2^n}} = \lg{(n!)} - n = \Omega(n\lg{n})$.

Thus none of the above m is linear.

8.1-4

In each subsequence, we need at least $\Omega(k\lg{k})$ comparisions, thus for $\frac{n}{k}$ subsequences, it needs $\frac{n}{k}\Omega(k\lg{k}) = \Omega(n\lg{k})$ comparisions.