\documentstyle[12pt,overhead]{article}
\begin{document}
\input{epsf}
\input rotate
\epsfverbosetrue
%\baselineskip=40pt
\large





\newcommand{\programbegin}{\begin{tabbing} 
ww\=ww\=ww\=ww\=ww\=ww\=ww\=ww\=ww\=ww\=ww\=ww\=ww\=ww\kill}
%
\newcommand{\Rtwo}{R$_2$}
\newcommand{\psim}{ ParCon }
\newcommand{\osim}{ ParOpt }
\newcommand{\Ltwo}{L$_2$}
\newcommand{\Lone}{L$_1$}
\newcommand{\programend}{\end{tabbing}}
\newcommand{\pprocedure}{\mbox{\bf procedure\ }}
\newcommand{\pfunction}{\mbox{\bf function\ }}
\newcommand{\pbegin}{\mbox{\bf begin\ }}
\newcommand{\pend}{\mbox{\bf end\ }}
\newcommand{\pif}{\mbox{\bf if\ }}
\newcommand{\pthen}{\mbox{\bf then\ }}
\newcommand{\pelse}{\mbox{\bf else\ }}
\newcommand{\pendif}{\mbox{\bf endif\ }}
\newcommand{\pfor}{\mbox{\bf for\ }}
\newcommand{\pto}{\mbox{\bf to\ }}
\newcommand{\pendfor}{\mbox{\bf endfor\ }}
\newcommand{\pendforall}{\mbox{\bf endforall\ }}
\newcommand{\pdo}{\mbox{\bf do\ }}
\newcommand{\pwhile}{\mbox{\bf while\ }}
\newcommand{\pendwhile}{\mbox{\bf endwhile\ }}
\newcommand{\pwhere}{\mbox{\bf where\ }}
\newcommand{\pstruct}{\mbox{\bf struct\ }}
\newcommand{\pint}{\mbox{\bf int\ }}
\newcommand{\penum}{\mbox{\bf enum\ }}
\newcommand{\pforall}{\mbox{\bf for all\ }}
\newcommand{\send}{\mbox{\bf send\ }}
\newcommand{\sendw}{\mbox{\bf sendw\ }}
\newcommand{\recv}{\mbox{\bf recv\ }}
\newcommand{\recvw}{\mbox{\bf recvw\ }}
\newcommand{\pexit}{\mbox{\bf exit\ }}
\newcommand{\pbreak}{\mbox{\bf break\ }}
\newcommand{\por}{\mbox{\bf or\ }}
\newcommand{\pand}{\mbox{\bf and\ }}
%
\newcommand{\nbyrp}{\left\lceil\frac{n}{\sqrt p}\right\rceil}
\newcommand{\rel}{\mbox{$\ \prec\ $}}
\newcommand{\mbyp}{\left\lceil\frac{m}{p}\right\rceil}
\newcommand{\mop}{\frac{m}{p}}
\newcommand{\typevertex}{\mbox{$0\,..\,n-1$}}
\newcommand{\typeedge}{\mbox{$0\,..\,\mbyp-1$}}
\newcommand{\eqb}{\begin{eqnarray}}
\newcommand{\eqe}{\end{eqnarray}}
%\newcommand{\tabsfigure}{wwwwww\=wwwwww\=wwwwww\=wwwwww\=wwwwww\=wwwwww\=wwwwww\=wwwwww\=wwwwww\=wwwwww\= \kill}
%
\newcommand{\eqnb}{\begin{eqnarray}}
\newcommand{\eqne}{\end{eqnarray}}
\newcommand{\mat}{$\ ^\spadesuit$}
\newcommand{\edgel}{$\ ^\clubsuit$}
\newcommand{\adlmat}{$\ ^\dagger$}
\newcommand{\dedgel}{$\ ^\ddagger$}
\newcommand{\whatd}{$\ ^\perp$}
\newcommand{\orderlogp}{${\rm O}(\log p)\,$}
\newcommand{\orderlogrlogstarr}{${\rm O}(\log r \log^* r)\,$}
\newcommand{\orderlogn}{${\rm O}(\log n)\,$}
\newcommand{\ordernlogn}{${\rm O}(n \log n)\,$}
\newcommand{\orderp}{${\rm O}(p)\,$}
\newcommand{\ordern}{${\rm O}(n)\,$}
\newcommand{\orderr}{${\rm O}(r)\,$}
\newcommand{\orderone}{${\rm O}(1)\,$}
\newcommand{\nbylogn}{$\frac n {\log n}\,$}
\newcommand{\ordernbylogn}{${\rm O}\!\!\left(\frac n {\log n}\right)\,$}
\newcommand{\rbylogrlogstarr}{$\frac r {\log r \log^* r}\,$}
\newcommand{\thetap}{$\Theta (p)\ $}
\newcommand{\thetalogn}{$\Theta (\log n)\ $}
\newcommand{\thetalogr}{$\Theta (\log r)\ $}
%
\newcommand{\lp}{{\large \bf  (}}
\newcommand{\rp}{{\large \bf  )}}
%
\newenvironment{hangref}{\begin{list}{}{\setlength{\itemsep}{0pt}
\setlength{\parsep}{0pt}\setlength{\leftmargin}{+\parindent}
\setlength{\itemindent}{-\parindent}}}{\end{list}}


\begin{slide}{}{}
\baselineskip=40pt
\section{\bf \LARGE SORTING BY RANKING}
  \begin{description}
  \baselineskip=40pt
%  \item Sorting by Ranking\\
   \item \{{\bf rank} of an item=number of items smaller\}\\
 
   rank each item by counting;\\
   then place each item according to its rank.\\
	 If duplicate, then
   place it at the nearest slot to the right.\\

      \item $W(n)=O(n(n-1))=A(n)=B(n)$\\

      \item $S(n)=O(n)$
   \end{description}

To handle duplicates, redefine\\
rank(i) = number of items smaller than i or, if equal, 
occurring before i.\\
Oblivious Algorithm
\end{slide}


\begin{slide}{}{}
\baselineskip=40pt
\section{\bf \LARGE  SORTING BY SWAPPING}
	 \begin{description}
	   \item {\bf Bubble Sort}--good when input is nearly sorted\\
                $W(n)=O(n^{2}/2)$\\
                $S(n)=O(1)$\\
	   \item {\bf  Odd-Even Exchange Sort}
	     \begin{description}    
	       \item a) odd-even compare \& exchange
      	       \item b) even-odd compare \& exchange  
               \item c) repeat step (a) and (b) if exchange-count $>0$
	     \end{description} 
               $W(n)=O(n^{2})$ \\
               $S(n)=O(1)$\\                                                   
         \end{description}
\end{slide}


\begin{slide}{} {}
\baselineskip=40pt
\section{\bf \LARGE SORTING BY INSERTION}
Online algorithms.
            \begin{description}
              \item {\bf   Linear Insertion Sort}\\
                Insert the next element in the ordered list prepared
		so far  by
                sequential search \& shifting.  \\[2in]
                $W(n)=O(n^2/2)$\\
                $S(n)=O(1)$\\
		$O(n)$ time on a sorted list 
              \item {\bf  Binary Insertion sort}\\
		   perform binary search to find location for insertion.\\
		$W(n) = O(n\log n) + O(n^2)$. 
	      \item {\bf  Tree Sort}\\
        	   Insert into a binary search tree, then       
			traverse tree in-order. \\[2in]	        
               $W(n)=O(n^{2})$\\
               $S(n)=O(n)$\\
	       $A(n)=B(n)=O(n \log n) + O(n)$	
         \end{description}
\end{slide}


\begin{slide}{}{}
\baselineskip=40pt
\section{\bf \LARGE  SORTING BY SELECTION}
\baselineskip=34pt
	 Offline algorithms
	\begin{description}
	      \item {\bf  Selection sort} \\
                 find maximum \& replace with the concurrent 
		last\\[2in]
               $W(n)=O(n^{2})$\\
               $S(n)=O(1)$\\
               $O(n^{2})$ even on a sorted list
\newpage
	      \item{\bf Tournament Sort} \\[3in]
               $W(n)=A(n)=B(n)=O(n \log n)$\\
               $S(n)=O(n)$ for the tournament tree             
	      \item{\bf  Heap Sort}
		\begin{itemize}
	         \item construct a max heap                   -$O(n)$ 
                 \item delete root and update heap repeatedly -$O(n\log n)$
		\end{itemize}
                $W(n)=A(n)=O(n \log n)$\\
                $S(n)=O(1)$ \\
             \end{description}
\end{slide}


%\begin{slide}{Sorting by Selection}{Heapsort}
      	%\begin{description}
                    %\item Construction\\
                         %$\sum_{l=0}^{ \log n-1} (\log n-l)2^{l} = O(n)  $ (See pp. 145)
                    %\item    Or,\\
                                %$c(n)= 2c(n/2)$ (construct left and right sub-heaps) $+ 2 \log n$ (restore root)
          %\end{description}
 		%Restore Heap: -$o(h)$ 
          %\begin{description}
                %\item       $h=$height of the heap
          %\end{description}
%\end{slide}


\begin{slide}{}{}
\baselineskip=40pt
\subsection{\bf Heap Sort} 
	          \begin{itemize} 
			\item Restore-Heap(i):  $O(h)$ where $h$ is the
				height of the node i.\\[2in]
		        \item Construct Heap:    \\
				\ \ \ \ For $i = \left \lfloor \frac n 2 \right \rfloor$ down to 1 \ \ \ \ Restore-Heap(i)\\
 $O(n)$\\[2in]
		        \item Heap Sort:\\
			\begin{enumerate}
			\item Construct Heap  \hfill -- $O(n)$
			\item For $i$:=$n$ down to $2$\hfill  -- $O(n \log n)$\\
                                \ \ \ \ exchange $L[1]$ with $L[i]$\\
				\ \ \ \ decrement heap size\\
                                \ \ \ \ Restore-Heap($1$) 
			\end{enumerate}
\item Time Complexity of deletion phase in Heap Sort\\
\begin{eqnarray*}
                    W(n)& =& 2 \log n+W(n-1)\\
                                &=&2\sum_{i=1}^{n}\log i\\
                        &\leq &2\int_1^{n+1}\log x dx\\[1.5in]
				&=&\left[2(x\log x-x)
					\right]_{1}^{n+1}\\
			        &=& 2n \log n-2n
\end{eqnarray*}
                  \end{itemize}


\end{slide}
\begin{slide}{}{}
\baselineskip=40pt
\subsubsection{\bf Heapsort Construction}
                Construct Heap: 
          \begin{description}
                  \item      for $i= \lfloor n/2 \rfloor$ downto $1$ 
		  \item		\ \ \ \ Restore-heap($i$)\\[2in]
	  \end{description}
Time Complexity of Iterative Algorithm for Heap Construction:
         $$\sum_{h=1}^{\lfloor\log n\rfloor}\lceil n/2^{h+1} \rceil O(h)$$\\ $$=O\left (n\sum_{h=1}^{\log n} (h/2^{h} )\right)$$\\
	 	     $=O(n)$ (pp. 135)\\[1cm]
		     Consider $\sum_{h=1}^{\log n}h/2^{h}$\\
\noindent  Let 
\begin{eqnarray}
 x&=& 1/2+2/2^{2}+3/2^{3}+4/2^{4}+ \cdots+y/2^{y}\\
            2x&=1+&2/2^{1}+3/2^{2}+4/2^{3}+\cdots+y/2^{y-1}\\
                        x&=1+&1/2+1/2^{2}+\cdots+1/2^{y-1}\\
&&-y/2^{y}\\
                          &=&\frac{(1/2)^{y}-1}{1/2-1}-y/2^{y}\\
                          &=&2(1-(1/2)^y)-y/2^{y}\\
                          &\leq 2\\
\end{eqnarray}
\end{slide}


\begin{slide}{}{}
%\baselineskip=40pt
\subsubsection{\bf Heapsort: Recursive Construction}
		        {\bf Construct-Heap(n):}
			\begin{description}
                           \item construct left subheap
			   \item construct right subheap
			   \item Restore-heap($1$)
                        \end{description}
	{\bf Time Complexity:}
\begin{eqnarray}
                        W(n) &=& 2w(n/2)+ \log n\\
                         &=&  \log n + 2w(n/2)\\
                         &=&  \log n + 2 \left (\log (n/2) + 2w(\frac {n/2}2)\right)\\
                         &=&  \log n + 2 \log n - 2\log 2 + \\
				&&2^2w({n/2^2})\\
                         &=&  \log n + 2 \log n - 2\log 2 + \\
				&&2^2\left (\log(\frac n {2^2}) +
				2w\left(\frac {n/2^2}2\right)\right)\\
                         &=&  \log n + 2 \log n - 2\log 2 + \\
                         &&+ 2^2 \log n - 2^2\log (2^2) + 
				2^3w({n/2^3})\\
			&& \cdots\\
                         &=&  \log n + 2 \log n - 2\log 2 + \\
                         &&+ 2^2 \log n - 2^2\log (2^2) + 
				 \cdots +\\
                          &&2^k \log n - 2^k\log (2^k) + 
				2^{k+1}w({n/2^{k+1}})\\
                             &= &\log n(1+2+2^{2}+\cdots+2^{k})\\
               &&-(2+2\cdot2^{2}+3\cdot2^{3}+\cdots +k\cdot2^{k})
\end{eqnarray}

\newpage
 Here, we assume that $n=2^k$ so $ k = \log n.$\\[1cm]
		        Let $s=2^{0}+2^{1}+2^{2}+\cdots+2^{k}$\\
			  $=\frac{2^{k+1}-1}{2-1}=2^{k+1}-1$ \\[1cm]
To derive this formula, one can follow these steps:\\
\begin{eqnarray}
		        s&=2^{0}+&2^{1}+2^{2}+\cdots+2^{k}\\
			2s&=& 2^{1}+2^{2}+\cdots+2^{k}+2^{k+1}\\
			s&=&-1+2^{k+1}
\end{eqnarray}
         		Thus, $\sum_{i=0}^{k} 2^{i}=2^{k+1}-1$\\[1cm]
	Likewise, let
\begin{eqnarray}
T&=1\cdot 2^{1}+&2\cdot 2^{2}+3\cdot2^{3}+\cdots+k\cdot2^{k}\\
	2T&= &1\cdot 2^{2}+2\cdot2^{3}+\cdots+\\
		&&(k-1)\cdot2^{k}+ k2^{k+1}\\
	T&=&-2^{1}-2^{2}-2^{3}-\cdots-2^{k}+\\
	&&k2^{k+1}\\ &	=&k2^{k+1}-(2^{1}+2^{2}+\cdots+2^{k})\\
        &=&k2^{k+1}-(2^{k+1}-2)\\
        &=&(k-1)2^{k+1}+2\\
\end{eqnarray}
        $\Rightarrow W(n)= \log n(2^{K+1}-1)-((k-1)2^{k+1}+2)$\\
        $=2n \log n- \log n-2n \log n+2n-2$\\
        $=2n- \log n-2$\\
	$=O(n)$								 			  	
	  %   \end{description}
\end{slide}

\begin{slide}{}{}
\baselineskip=40pt
\subsubsection{\bf Priority Queue employing Heap}
Read pp. 138 (Section 6.5)\\
Delete Max/Min\\
Insert\\
See Exercise 6-1, pp. 142
\end{slide}




\begin{slide}{}{}
\section{\bf \LARGE  SORTING BY MERGING}
	   
 		\begin{itemize}
		  \item {\bf Mergesort}\\
			\begin{itemize}
                        \item $W(n)=O(n)+2w(n/2)$\\
		             $=n+2w(n/2)$\\
			     $=n+2(n/2+2w(n/2^{2})$\\
			     $=n+n+2^{2}w(n/2^{2})$\\
			     $=2n+2^{2}w(n/2^{2})$\\
			     $=2n+2^{2}(n/2^{2}+2w(n/2^{3}))$\\
			     $=3n+2^{3}w(n/2^{3})$\\
			$\cdots$\\
			     $=kn+2^{k}w(n/2^{k})$\\\
			$w(n/2^{k})=w(1)=0$\\
                        $n/2^{k}=1$, $k= \log_{2} n$\\
                        $\Rightarrow W(n)=\theta(n \log n)$\\       
			\item Recursion tree for $W(n)$
			\item $S(n)=O(n)$\\
                        Can be reduced to $O(1)$ but algorithm slows down.\\
		        A temporary array of half the size is required, however.
			\end{itemize}
		\end{itemize}
\end{slide}


\begin{slide}{}{}
\baselineskip=40pt
\section{\bf \LARGE SORTING BY SPLITING}
$W(n) = O(n^2)$ but $A(n) = O(n\log n)$\\[1cm]
         
                Quicksort $(A,p,r)$:
          	\begin{description}
                    \item if $p<r$ then $q\leftarrow$ Partition$(A,p,r)$\\
                             Quicksort$(A,p,q)$\\
                             Quicksort$(A,q+1,r)$
		\end{description}
\end{slide}
\begin{slide}{}{}
\baselineskip=40pt
\subsection {\bf Quicksort: Partitioning}
	{\bf Partition I.}\\[0.5cm]
	\programbegin
		$x:=A[p]$; $i:=p-1$; $j:=r+1$\\
	\pwhile (TRUE) \pdo \\	
	
	   \ \ {\bf Repeat} Decrement j {\bf until} $A[j] \leq x$\\
	   \ \ {\bf Repeat} Increment i {\bf until} $A[i] \geq x$\\
	   \ \ {\bf if} $i<j$\\
               \ \ \ \  {\bf then} exchange $A[i]$ and $A[j]$\\
	       \ \ \ \ {\bf else} return $j$\\
	\pendwhile
	\programend
\newpage
           $x=15$\\
	     15\  7\   23\  5\  20\  3\\[3in]

             %$\uparrow$           $\uparrow$\\ 
	     %i			j
 	     %3   7   23  5  20  15\\
                     %$\uparrow$  $\uparrow$\\   
		     %$q$   $j$\\
	     %3   7   5   23 20  15\\
Why do $i$ and $j$ never get out of array bounds?\\
$W(n) = n + 2$ comparisons 
\end{slide}


\begin{slide}{}{}
		$W(n)=O(n^{2})=O(n)+W(n-1)$\\[1.5in]

                $B(n)=O(n)+2B(n/2)=O(n \log n)$\\

\end{slide}
\begin{slide}{\bf Balance Partitioning:}{} 
\begin{itemize}
\item Even if each split is 1\% on one side and 99\% on the other,
      recursion tree remains logarithmic.\\[1.5in]
\item Alternate good and bad splits:\\[1.5in]
\end{itemize}
\end{slide}
\begin{slide}{\bf Quicksort Improvements}{} 
                \begin{description}
                   \item    -- random x
		   \item    -- median of      first, middle and last items
		   \item    -- insertion sort for $n \leq 15$
		\end{description}
		$S(n)=O(n)$\\
		(See 7-4; reduces $S(n)$ to $O(\log n)$)
\end{slide}


\begin{slide}{}{}
\baselineskip=40pt
\subsection{\bf Quicksort: Partitioning II}{}

\programbegin
Input: A[p..r]\\
Invariants: \{All items  in $A[2..i]$ are $<$ the pivot.\} \\
\{All items in $A[(i+1)..(unknown-1)]$ are $\geq $ the pivot\}\\
$x = A[p]; \ i := p;$\\
\pfor  $unknown := p+1$ \pto $r$ \pdo\\
\ \ \ \pif $A[unknown] < x$ \pthen \\
\ \ \ \ \ \ \ \ \ $i := i+1$; swap$(A[i],A[unknown])$ \\
swap$(A[1],A[i])$
\programend
		$W(n)=n-1$ comparisons\\
			
\newpage
			15  \ 7  \ 23  \ 5  \ 20  \ 3\\[3in]
                        %$\uparrow$   $\uparrow$\\
			%i   u\\
			%15  7  23  5  20  3\\
                            %$\uparrow$  $\uparrow$\\
			    %i  u\\
			%15  7  5  23  20  3\\
                            %$\uparrow$   $\uparrow$\\
			    %i         u\\
			%15  7  5  23  20  3\\
                               %$\uparrow$    $\uparrow$\\
			       %i          u\\
			%15  7  5  3   20  23\\
                                  %$\uparrow$\\
				  %i\\
                        %3   7  5  15  20  23\\
	%	
\end{slide}


\begin{slide}{}{}
%\baselineskip=40pt
\subsection{\bf Av. Case Complexity of Quicksort}
\baselineskip=30pt
	Assume  
               \begin{itemize}
                \item all  keys distinct
		\item all  permutations equally likely
	       \end{itemize}
        Probability that split point is $i$,
	   for $1\leq i \leq n$, is $1/n$\\[1cm]
\begin{eqnarray*}
		&&A(n)=(n-1) +\frac 1 n (A(0)+A(n-1)+\\
	&& A(1)+A(n-2)+ \cdots A(n-1)+A(0))\\
		    &&=n-1+\frac 2 n\left (A(0)+A(1)+\cdots+A(n-1)\right )\\
                &&A(n)=n-1+ \frac 2 n \Sigma_{i=2}^{n-1} A(i), \ \ A(0)=A(1)=0\\                
                &&(n)A(n)=(n)(n-1)+2\Sigma_{i=2}^{n-1} A(i) \\
             &&A(n-1)=n-2+\frac{2}{n-1}\Sigma_{i=2}^{n-2} A(i) \\        
                &&(n-1)A(n-1)=(n-1)(n-2)+2\Sigma_{i=2}^{n-2} A(i) \\
		&&nA(n)-(n-1)A(n-1)\\
		&& =n(n-1)-(n-2)(n-1)+2A(n-1)\\
		&&nA(n)-(n+1)A(n-1)=2(n-1)\\
         &&\frac{A(n)}{n+1}-\frac{A(n-1)}{n}=\frac{2(n-1)}{n(n+1)}  \\
\end{eqnarray*}
	Let $B(n)=\frac{A(n)}{n+1}$  ({\em Changing Variable})\\
	     Since $A(1)=0$, $B(1)=0$\\
\begin{eqnarray*}
        &&\Rightarrow B(n)-B(n-1)=\frac{2(n-1)}{n(n+1)}\\
                &&B(n)=\frac{2(n-1)}{n(n+1)}+B(n-1) \\
                &&=\frac{2(n-1)}{n(n+1)}+\left (\frac{2(n-2)}{(n-1)(n)}+B(n-2)\right) \\
            &&=B(1)+\frac{2 \cdot 1}{2 \cdot 3}+\frac{2 \cdot 2}{3 \cdot 
             4}+\cdots + \frac{2(n-1)}{n(n+1)}, B(1) = 0\\
            &&B(n)=\sum_{i=2}^{n} \frac{2(i-1)}{i(i+1)}\\
\end{eqnarray*}
        $f(n)\  =\ \frac{2(n-1)}{n(n+1)}$
         continuous decreasing function
\begin{eqnarray*}
        &&B(n)\leq \int_{2}^{n} f(x)dx, \ \ \ f(1)=0\\
        &&\frac{2(x-1)}{x(x+1)} =\frac{A}{x}+\frac{B}{x+1}\\
        &&=\frac{(A+B)x+A}{x(x+1)}\\
        &&\Rightarrow A=-2\\
                &&A+B=2\\
        &&\Rightarrow B=4\\
        &&\Rightarrow f(x)=\frac{4}{x+1}-\frac{2}{x}\\
        &&\int_{2}^{n} f(x)dx=\int_{2}^{n} \left (\frac{4}{x+1}-\frac{2}{x}\right)dx\\
        &&=\left (4\ln (x+1)-2\ln x\right ) |_{2}^{n}\\
        &&=4\ln(n+1)-2\ln n -4\ln3+2\ln 2\\
        &&\approx 2\ln n\\
        &&\Rightarrow B(n)\leq 2\log n\\
        &&A(n)=(n+1)B(n)\leq 2(n+1)\ln n\\[0.5cm]
        &&\Rightarrow A(n)\leq 1.4(n+1)\log_{2} n
\end{eqnarray*}
\end{slide}



\begin{slide}{}{}
\section{\bf \LARGE LOWER BOUND}
        \begin{description}
         \item (a) Local exchange only\\
		\begin{description}
                  \item each accomplishes in undoing one inversion\\
                   5 1 4 7 2 has inversions (5,1),(5,4),(5,2),(4,2),(7,2)\\
                   (n n-1 \ldots 2 1) has $n(n-1)/2$ inversions\\
                        $\Rightarrow O(n^{2}/2)$ lower bound
	        \end{description}  
         \item (b) lower bound on comparison based sorting\\
	 example: a b c - there are 3! outputs.\\
	 (for n numbers there are n! outputs) \\
  	 Every decision tree to sort n numbers must have atleast n! leaf nodes \\
  	 Every decision tree to sort n numbers must have atleast 2n! - 1 nodes \\
  	 Every decision tree to sort n numbers must have depth atleast $\log_{2} n! $ leaf nodes  \\
	 Depth is the lower bound worst case time complexity for this class of algorithms \\
         $\log_{2} n!=log_{2} (n * (n-1) * (n-2) * (n-3) ...... 1) $\\
         $\log_{2} n!=log_{2} (n) +  log_{2} (n-1) + log_{2} (n-2) + log_{2} (n-3) ...... + log_{2} (1) $\\
         $\log_{2} n!=\sum_{j=1}^{n} \log_{2} j $\\
         $\leq \int_{1}^{n} \log_{2} xdx$\\
         $=(x\log x -x)|_{1}^{n}$\\
         $=n\log n -n$
        \end{description}
        Lower Bound on Comparison-Based Sorting Algorithm\\
        Decision Tree for 3 numbers\\[2in]
%Figer 1
	\begin{figure}[htb]
	\begin{center}
	\leavevmode\epsfxsize12cm\epsfbox{tmp.eps}
	\end{center}
	\end{figure}

        Depth of binary tree with $n!$ leaves \\
        $\geq \log_{2} n!$\\
        $\geq \int \log x dx$\\
        $\geq n\log n-1.5n$\\
\end{slide}


\begin{slide}{}{}
\section{\bf \LARGE SHELL SORT (Donald Shell)}
        Sort subarray comprising every $h_i$ location, for a few selected hop sizes $h_i$, $k \geq i \geq 1$, and final $h_1 = 1$\\
             $h_{1}=1$ always use insertion sort for sorting\\[0.5cm]
             with $h_{2}=1.72n^{1/3}$\\

             $W(n)=(\frac{n}{1.72n^{1/3}})^{2}+1.72n^{1/3}+n^{2}$\\
                  $=\frac{n^{2}}{1.72n^{1/3}}+n^{2}$\\
                  $=\frac{n^{5/3}}{1.72}+n^{2}$\\
                  $=O(n^{2})$\\

           for $h_{k}=2^{k}-1$, $1\leq k\leq \lfloor\log n\rfloor$\\
             $W(n)=O(n\root{n})$\\

             $2^{5}-1=31=(11111)_{2}$\\
             $2^{4}-1=15=(1111)_{2}$\\

             for $h_{k}$ is an integer of the form $2^{i}3^{j},h_{k}<n$\\
             $W(n)=O(n(\log n)^{2})$\\

             $2^{0}3^{0},2^{1}3^{0},2^{0}3^{1},2^{1}3^{1},2^{2}3^{1}$\\
             1    2    3    6    12\\
             too many $h_{k}'$s, hence overhead is large.
\end{slide}
\end{document} 
	
