\documentclass[11pt]{article}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{fullpage}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}

\newenvironment{proof}{\noindent {\bf Proof.}}%
                      {$\Box$}

\newcommand{\eli}{\>}


\begin{document}


\title{Solution of Exercise 6, Question 4(b)}

\author{Elad Verbin}

\maketitle

\underline{Question:} You are given an array of size $n$ with
$\log n$ distinct integers, each one appearing exactly
$\frac{n}{\log n}$ times. Prove a lower bound of $\Omega(n \log
\log  n)$ in the comparison model for any algorithm which sorts
such an array.

\noindent \underline{Answer:} First, assume that the $\log n$
distinct values in the input array are $1, \ldots, \log n$. This
does not matter for an algorithm in the comparison model, because
such an algorithm only performs comparisons between elements. Now,
how many possible inputs are there? If all elements were distinct
then the number of inputs would have been $n!$. However, in our
case we need to divide by the number of permutations that will
keep the array the same. Thus, the number of possible inputs is
exactly
\begin{equation*}
X=\frac{n!}{(\frac{n}{\log n} !)^{\log n}}
\end{equation*}

Now, let us look at some algorithm in the comparison model, that
is a decision tree that performs only comparisons. How many leaves
must it have? It is easily seen that a solution can be a correct
solution only for one input array. Therefore the algorithm must
have at least $X$ leaves. It is a tree where every vertex has 2 or
3 children, and which has at least $X$ leaves, so its depth is at
least $\Omega(\log (X))$. Therefore, the running time of any
algorithm in the comparison model is at least $\Omega(\log (X))$.
Now we wish to prove that $\log (X) = \Omega(n \log \log n)$.

First, let us assume that for every $m$, $m!=2^{m \log m}$ and in
this case we will easily get that $\log (X) = \Omega(n \log \log
n)$. The assumption that $m!=2^{m \log m}$ is untrue, of course,
but the math here is conceptually the right math, and it is
cleaner than the correct proof we will give later. So:
\begin{align*}
\log (X) = & \log \left( \frac{n!}{(\frac{n}{\log n}!)^{\log n}}
\right) =
 \log (n!) - \log ((\frac{n}{\log n}!)^{\log n}) = n \log n -
(\log n) \log (\frac{n}{\log n}!) = \\
& n \log n - (\log n) \frac{n}{\log n} \log (\frac{n}{\log n}) = n
\log n - n (\log n - \log \log n) = n \log \log n \ ,
\end{align*}
as required.

%Now, let us see that using the (correct) fact that $m!=2^{\Theta(m
%\log m)}$ or, in other words, $\log (m!)=\Theta(m \log m)$, does
%not give the required result:
%\begin{align*}
%\log (X) = & \log \left( \frac{n!}{(\sqrt{n}!)^{\sqrt{n}}} \right)
%= \\
%& \log (n!) - \log ((\sqrt{n}!)^{\sqrt{n}}) = \Theta(n \log n) -
%\sqrt{n} \log (\sqrt{n}!) = \\
%& \Theta(n \log n) - \Sqrt{n} \Theta(\sqrt{n} \log (\sqrt{n})) =
%\Theta(n \log n) - \Theta(n \log n) = ??? \ .
%\end{align*}
%As you see, we can't get an answer here.\footnote{Specifically,
%computing a difference between Thetas is undefined, since it can
%have many answer: $0=10n-10n=\Theta(n)-\Theta(n)$, but also
%$n=11n-10n=\Theta(n)-\Theta(n)$. This is much like the situation
%is Discrete Math, where the difference of two cardinalities
%(OTZMOT) is not defined: $\aleph - \aleph$ may be $0$ or $\aleph$
%or $\aleph_0$ or a finite number, depending on the choice of
%representatives.}

So, how do we formally prove that $\log (X) = \Omega(n \log n)$ in
a correct way? We use Stirling's approximation. Stirling's
approximation states that
\begin{equation*}
n! \sim \sqrt{2 \pi n} \left( \frac{n}{e} \right)^n \ .
\end{equation*}
In other words this says that
\begin{equation*}
\lim_{n \rightarrow \infty} \frac{n!}{\sqrt{2 \pi n} \left(
\frac{n}{e} \right)^n} = 1 \ .
\end{equation*}
But we will be satisfied using the weaker, but still useful
expression
\begin{equation*}
n! = \Theta\left( \sqrt{n} \left( \frac{n}{e} \right)^n \right) \
.
\end{equation*}
From taking the logarithm of both sides of this expression it
follows that
\begin{equation*}
\log (n!) = n \log n \pm O(n) \ .
\end{equation*}
We now give a proof that $\log (X) = \Omega(n \log \log n)$:
\begin{align*}
\log (X) = & \log \left( \frac{n!}{(\frac{n}{\log n}!)^{\log n}}
\right)
= \\
& \log (n!) - \log ((\frac{n}{\log n}!)^{\log n}) = n \log n \pm
O(n) - (\log n) \log (\frac{n}{\log n}!) = \\
& n \log n \pm O(n) - (\log n) (\frac{n}{\log n} \log
(\frac{n}{\log n}) \pm
O(\frac{n}{\log n})) =\\
& n \log n \pm O(n) - n (\log n - \log \log n) \pm O(n) = n \log
\log n \pm O(n) = \Theta(n \log \log n) \ .
\end{align*}


\section{Further Reading}

Here are some web pages about lower bounds, which you might find
interesting.

\subsection{The ``P=NP?'' Question}
\verb+http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP+\\
\verb+http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf+\\
\verb+http://www.win.tue.nl/~gwoegi/P-versus-NP.htm+\\
\verb+http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/W06/w06.pdf+\\

\subsection{Stirling's Approximation}
\verb+http://hyperphysics.phy-astr.gsu.edu/Hbase/Math/stirling.html+\\
\verb+http://en.wikipedia.org/wiki/Stirling's_approximation+\\

%\subsection{About the 3-SUM problem}
%\verb+http://en.wikipedia.org/wiki/3SUM+\\
%\verb+http://geomblog.blogspot.com/2004/03/3sum.html+\\

\subsection{About lower bounds in computer science}
Lecture notes L,H and J in
\verb+http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/+\\

\end{document}
