Vrftjkry

I'm working on a homework problem that has me showing a "$Omega(nlog 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)dotsleft(dfrac{k}{2}right)$

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

(4)$qquad geq
left(dfrac{k}{2}right)left(dfrac{k}{2}right)ldotsleft(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}logleft(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).

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 1gt 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!$

By definition,

$$k!=kcdot(k-1)cdot,cdots,cdot(k-(k-2))cdot(k-(k-1))=kcdot(k-1)cdot,cdots,cdot2cdot1$$
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/jle i$ as long as $jgeq 1$).

Here, we have

$$k!=kcdot(k-1)cdot,cdots,cdot 3cdot2cdot1geq kcdot(k-1)cdot,cdots,cdot 3cdot2geq kcdot(k-1)cdot,cdots,cdot3$$

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

$$k!geq underbrace{k}_{geq k/2}cdotunderbrace{(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

$$kcdot(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/2rceil$ elements in this product (where $lceil k/2rceil$ denotes the closest upper integer, e.g. $lceil 5/2rceil=lceil 2.5rceil=3$). Suppose it is true for $k$, we have to show it for $k+1$. The product is then

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

so that the product for $k+1$ contains $lceil k/2rceil+1$ elements. But $lceil (k+1)/2rceil=lceil k/2+1/2rceil=lceil k/2rceil+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/2rceil+1=lceil (k+1)/2rceil$ elements.

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

$$k!geq underbrace{k}_{geq k/2}cdotunderbrace{(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/2rceil}geqleft(frac{k}{2}right)^{ (k/2)}$$