How to show that for all k, $k! \ge (k/2)^{k/2}$

Question

I'm working on a homework problem that has me showing a "$\Omega(n\log k)$ lower bound on the number of comparisons needed to sort a sequence of $n$ elements, when the input sequence consists of $\frac{n}{k}$ subsequences each containing $k$ elements. Each element in a subsequence will be larger than its preceding subsequence and smaller than its succeeding subsequence."

Essentially, I just need to sort $k$ elements in each of the $\dfrac{n}{k}$ subsequences.

I realize that to do this I need to show that the maximum possible height of a binary tree $2^h \geq (k!)^{n/k}$. I did this to try and solve it (assuming we are using $\log_2x)$:

$\log(2^h) \geq \log((k!)^{n/k})$

$h \geq \dfrac{n}{k}\log(k!)$

This is as far as I got. However, my professor told me that in order to solve the problem I would need to prove that for all $k$, $k! \geq \left(\dfrac{k}{2}\right)^{k/2}$

I can obviously see why this would be true, but I don't really know how to prove it. Looking it up online I found an answer that someone posted stating:

(1)$\qquad$ $k! = k(k-1)(k-2)\ldots(2)(1)$

(2)$\qquad$ $k! \geq k(k-1)(k-2)\dots\left(\dfrac{k}{2}\right)$

(3)$\qquad$ $k! \geq k(k-1)(k-2)\ldots\left(\dfrac{k}{2}\right) \geq \left(\dfrac{k}{2}\right)\left(\dfrac{k}{2}\right)\ldots\left(\dfrac{k}{2}\right)$

(4)$\qquad \geq \left(\dfrac{k}{2}\right)\left(\dfrac{k}{2}\right)\ldots\left(\dfrac{k}{2}\right) = \left(\dfrac{k}{2}\right)^{k/2}$

For (2), half of terms are greater than $\frac{k}{2}$ and half are smaller drop all terms less than $k$

Since $\dfrac{k}{2} \geq k$ we can write (3)

From this answer I know that by plugging in $\dfrac{k}{2}$ for $k!$ in the original equation will give me the answer $\dfrac{n}{2}\log\left(\dfrac{k}{2}\right)$. But I don't understand why we dropped half of $k!$ and how we could know that $\dfrac{k}{2} \geq k$. I understand part (4) but I don't really understand the transformations taking place in between (1) and (2), and (2) and (3).

Answer 1

It often helps to do a small concrete example. Let us do $k=8$. We are trying to show that $8! \gt 4^4$ You have $8!=8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$ The first $4$ factors are all greater than $4$ and the last four factors are all at least. $1$ So $8!=8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\gt 4 \cdot 4 \cdot 4 \cdot 4 \cdot 1 \cdot 1 \cdot 1 \cdot 1=4^4$ The same thing is happening in the general proof. The first $\frac k2$ terms in the factorial are greater than $\frac k2$ and the last $\frac k2$ terms are at least $1$. When we replace the terms, we are decreasing the product. When we wind up with $(\frac k2)^{(\frac k2)}$ we know that is smaller than $k!$

Answer 2

By definition,

$$k!=k\cdot(k-1)\cdot\,\cdots\,\cdot(k-(k-2))\cdot(k-(k-1))=k\cdot(k-1)\cdot\,\cdots\,\cdot2\cdot1$$ Every factor in this product is strictly positive and greater or equal to $1$, so that if you drop any factor, the resulting product will be less or equal than the initial one (since dropping a factor is equivalent to divide the initial product by this factor: this factor being greater or equal to $1$, we obtain an inferior quantity because if $i>0$, we have $i/j\le i$ as long as $j\geq 1$).

Here, we have

$$k!=k\cdot(k-1)\cdot\,\cdots\,\cdot 3\cdot2\cdot1\geq k\cdot(k-1)\cdot\,\cdots\,\cdot 3\cdot2\geq k\cdot(k-1)\cdot\,\cdots\,\cdot3$$

Etcaetera. We get $k!\geq k\cdot(k-1)\cdot\,\cdots\,\cdot (k/2)$. For any $0\le j\leq (k/2)$, it is clear that $k-j\geq k/2$, so that $k\geq k/2$, $k-1\geq k/2$, ..., $k-k/2+1\geq k/2$. It leads to

$$k!\geq \underbrace{k}_{\geq k/2}\cdot\underbrace{(k-1)}_{\geq k/2}\cdot\,\cdots\,\cdot \underbrace{(k-k/2+1)}_{\geq k/2}\cdot (k/2)\geq \left(\frac{k}{2}\right)^{\alpha}$$

where $\alpha$ is the number of elements in the following product

$$k\cdot(k-1)\cdot\,\cdots\,\cdot (k-k/2+1)\cdot (k/2)$$

If $k=2$, there is one element in the product. If $k=3$, there are two elements in the product. We claim that there are $\lceil k/2\rceil$ elements in this product (where $\lceil k/2\rceil$ denotes the closest upper integer, e.g. $\lceil 5/2\rceil=\lceil 2.5\rceil=3$). Suppose it is true for $k$, we have to show it for $k+1$. The product is then

$$(k+1)\cdot k\cdot(k-1)\cdot\,\cdots\,\cdot (k-k/2+1)\cdot (k/2)=(k+1)\underbrace{\left[k\cdot(k-1)\cdot\,\cdots\,\cdot (k-k/2+1)\cdot (k/2)\right]}_{\text{contains } \lceil k/2\rceil \text{ by hypothesis}}$$

so that the product for $k+1$ contains $\lceil k/2\rceil+1$ elements. But $\lceil (k+1)/2\rceil=\lceil k/2+1/2\rceil=\lceil k/2\rceil+1$ because $k$ is a natural number so that if $k=2n$ it is clear, and if $k=2n+1$, $k+1=2(n+1)$ and it is also clear. We proved that the product for $k+1$ contains $\lceil k/2\rceil+1=\lceil (k+1)/2\rceil$ elements.

It means that $\alpha=\lceil k/2\rceil$. Since $\lceil k/2\rceil\geq (k/2)$, we have

$$k!\geq \underbrace{k}_{\geq k/2}\cdot\underbrace{(k-1)}_{\geq k/2}\cdot\,\cdots\,\cdot \underbrace{(k-k/2+1)}_{\geq k/2}\cdot (k/2)\geq \left(\frac{k}{2}\right)^{\lceil k/2\rceil}\geq\left(\frac{k}{2}\right)^{ (k/2)}$$