\documentclass[10pt]{article}
\usepackage{newalg}
% \usepackage{mathrsfs}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{latexsym}

\oddsidemargin0cm
\topmargin-3cm     %I recommend adding these three lines to increase the 
\textwidth16.5cm   %amount of usable space on the page (and save trees)
\textheight23.5cm  

\begin{document}
 
\subsection*{}
\begin{tabular*}{1\textwidth}{@{\extracolsep{\fill}}lr}
Discussion 1&Dr. Nina Amenta\\
Thursday, January 12&ECS 222A, Winter 2005\\
\hline  % put a line under headers
\end{tabular*}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\subsection*{Asymptotic Notation} We begin by stating a few useful definitions.
\begin{itemize}
	\item[1.] If $f(n) = \Theta(g(n))$, then $\exists$ positive constants $c_1, c_2, n_0$ such that $0 \leq c_1g(n) \leq f(n) \leq c_2g(n)$, for all $n \geq n_0$.
	\item[2.] If $f(n) = O(g(n))$, then $\exists$ positive constants $c, n_0$ such that $0 \leq f(n) \leq cg(n)$, for all $n \geq n_0$.
	\item[3.] If $f(n) = \Omega(g(n))$, then $\exists$ positive constants $c, n_0$ such that $0 \leq cg(n) \leq f(n)$, for all $n \geq n_0$.
	\item[4.] If $f(n) = o(g(n))$, then $\exists$ positive constants $c, n_0$ such that $0 \leq f(n) < cg(n)$, for all $n \geq n_0$.
	\item[5.] If $f(n) = \Omega(g(n))$, then $\exists$ positive constants $c, n_0$ such that $0 \leq cg(n) < f(n)$, for all $n \geq n_0$.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Proof by Substitution} It is easy to complete a proof by substitution, and a bit harder to ascertain if you have found the best possible upper bound. For example, we will show that T(n)$ \leq an + T(9/10n)$ is $O(n \log{n})$ (which is not the best bound). In order to prove this, we will apply the substitution method, which is basically induction. We will assume that the asymptotic running time bound holds for small $n$, assume it is true for all $n \leq n'$, and then show that it is true for all $n > n'$. Thus, in this case, we assume $T(n) \leq cn\log{n}$.
\begin{align}
T(n) &= an + T(9/10n)\\
 &\leq an + c(9n/10)\log{(9n/10)}\\
 &= an + c(9n/10)(\log{(9/10)} + \log{n})\\
 &\leq an + c(9n/10)\log{n}\\
 &\leq an\log{n} + c(9n/10)\log{n}\\
 &\leq n\log{n}(a + 9/10c)
\end{align}

But what we want is to show that $T(n) \leq cn\log{n}$. Thus, we want:
\begin{align}
a + 9/10c &\leq c\\
a &\leq c/10\\
10a &\leq c
\end{align}

Thus, we have bounded $c$... as long as $c \geq 10a$, then $T(n) = O(n\log{n})$. But this is not the sharpest upper bound. Now, using the same methodology, we show that $T(n) = O(n)$.

\begin{align}
T(n) &= an + T(9/10n)\\
 &\leq an + c(9n/10)\\
 n(a + 9/10c) &\leq cn\\
a + 9/10c &\leq c\\
a &\leq c/10\\
10a &\leq c
\end{align}

Thus, again we have bound $T(n)$. By choosing $c \geq 10a$, then $T(n) = O(n)$. Note: when doing proofs by substitution, it is always important to remember the precise goal. For example, consider this \textbf{INCORRECT PROOF} that $T(n) = an + 2T(n/2)$ is $O(n)$.

\begin{align}
T(n) &= an + 2T(n/2)\\
 &\leq an + 2(cn/2)\\
 &\leq (a + c)n = O(n)
\end{align}

This is an absolutely true statement. $(a + c)n = O(n)$. However, what we needed to show was that $(a + c)n \leq cn$ for some choice of $c$. This will never be true. When we assume that $T(n) = O(n\log{n})$, the correct proof is as follows.

\begin{align}
T(n) &= an + 2T(n/2)\\
 &\leq an + 2(cn/2\log{n/2})\\
 &= an + cn(\log{n} - \log{2})\\
 &= an + cn(\log{n} - 1)\\
an + cn(\log{n} - 1) &\leq cn\log{n}\\
a + c(\log{n} - 1) &\leq c\log{n}\\
a - c + c\log{n} &\leq c\log{n}\\
a &\leq c
\end{align}

Thus, this equation is true for all $c \geq a$. Thus $T(n) = an + 2T(n/2)$ is $O(n\log{n})$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Random Search} The purpose of this example is to dervive some classic results in a very simple and clear way. In \textsc{RandomSearch}, we always have an array of size $n$, and we are looking for a particular element $x$ in that array, or an index $i$ such that $A[i] = x$. 

\begin{itemize}
	\item[a.] For this analysis, let us assume that we choose and replace. In other words, we choose a number $i$ at random from between 1 and $n$ each time (we toss the elements into a bag and pluck them out one by 1, returning them each time). If $A[i] = x$, we return, else we continue to choose and replace elements. In order to analyze the expected running time of our algorithm, let $Z$ be a random variable such that $Z$ equals the number of indices picked before $x$ is found. Since we allow indices to be choosen more than once, E[$Z$] can be calculated as follows:
\begin{align}
E[Z] &= {\sum_{z = 1}}^{\infty}{z\cdot{Pr[Z=z]}}\\
E[Z] &= 1\cdot{Pr[Z=1]} + 2\cdot{Pr[Z=2]} + 3\cdot{Pr[Z=3]} + \cdots\\
E[Z] &= 1\cdot{\frac{1}{n}}+2\cdot{\frac{n-1}{n}}\cdot{\frac{1}{n}}+3\cdot{\biggl({\frac{n-1}{n}}\biggr)^2}\cdot{\frac{1}{n}}+\cdots\\
E[Z] &= \frac{1}{n}(1 + 2\cdot{\frac{n-1}{n}} + 3\cdot{\biggl({\frac{n-1}{n}}\biggr)^2} + \cdots)\\
E[Z] &= \frac{1}{n}\sum_{j=0}^{\infty}(j+1){\biggl(\frac{n-1}{n}\biggr)}^{j}
\end{align}
We can simplify the expression for E[$Z$] by using the following result:
\begin{align}
\sum_{j=0}^{\infty}x^{j+1} &= x\sum_{j=0}^{\infty}x^{j}\\
 &= \frac{x}{1-x}\\
\frac{d}{dx}\biggl(\sum_{j=0}^{\infty}x^{j+1}\biggr) &= \sum_{j=0}^{\infty}(j+1)x^{j}\\
 &= \frac{1}{{(1-x)}^2}
\end{align}
Therefore, the E[$Z$] can be written in the following way:
\begin{align}
E[Z] &= \frac{1}{n}\frac{1}{{(1-\frac{n-1}{n})}^2}\\
E[Z] &= \frac{1}{n}\frac{1}{{\biggl(\frac{n-(n-1)}{n}\biggr)}^2}\\
E[Z] &= \frac{1}{n}\frac{1}{(\frac{1}{{n}^2})}\\
E[Z] &= n
\end{align}
This ia a bit surprising. Searching an array of size $n$ deterministically takes $O(n)$ time of course. But now we see that searching at random takes expected time $O(n)$ as well.
	\item[b.] Now, find the expected number of indices picked when each indice is inspected only once. In other words, we toss our elements into a bag, choose them 1 by 1, and discard each time if $A[i] \neq x$. Let $Z$ be a random variable such that $Z$ equals the number of indices picked before $x$ is found. E[$Z$] can be calculated as follows:
\begin{align}
E[Z] &= 1\cdot{Pr[Z=1]} + 2\cdot{Pr[Z=2]} + 3\cdot{Pr[Z=3]} + \cdots + n\cdot{Pr[Z=n]}\\
E[Z] &= 1\cdot{\frac{1}{n}}+2\cdot{\frac{n-1}{n}}\cdot{\frac{1}{n-1}}+3\cdot{\frac{n-1}{n}}\cdot{\frac{n-2}{n-1}}\cdot{\frac{1}{n-2}}+\cdots+n\cdot{\frac{n-1}{n}}\cdot{\frac{n-2}{n-1}}\cdots{\frac{1}{n-(n-1)}}\\
E[Z] &= 1\cdot{\frac{1}{n}}+2\cdot{\frac{1}{n}}+3\cdot{\frac{1}{n}}+\cdots+n\cdot{\frac{1}{n}}\\
E[Z] &= {\frac{1}{n}}(1+2+\cdots+n)\\
E[Z] &= {\frac{1}{n}}\cdot{\frac{n(n+1)}{2}}\\
E[Z] &= {\frac{n+1}{2}}
\end{align}
This is to be expected. In order to find the desired element, we have to look at about half.
\item[c.] For this analysis, we assume that $x$ is not unique in the array. In fact, we assume that the array $A$ contains $k$ $x$'s. As in part a, we choose and replace. Again, let $Z$ be a random variable such that $Z$ equals the number of indices picked before $x$ is found. Since there can now be multiple elements $k$ in the array that equal $x$, we modify the expression for E[$Z$] in the following way and use the result from part a to simplify:
\begin{align}
E[Z] &= 1\cdot{Pr[Z=1]} + 2\cdot{Pr[Z=2]} + 3\cdot{Pr[Z=3]} + \cdots\\
E[Z] &= 1\cdot{\frac{k}{n}}+2\cdot{\frac{n-k}{n}}\cdot{\frac{k}{n}}+3\cdot{\biggl({\frac{n-k}{n}}\biggr)^2}\cdot{\frac{k}{n}}+\cdots\\
E[Z] &= \frac{k}{n}(1 + 2\cdot{\frac{n-k}{n}} + 3\cdot{\biggl({\frac{n-k}{n}}\biggr)^2} + \cdots)\\
E[Z] &= \frac{k}{n}\sum_{j=0}^{\infty}(j+1){\biggl(\frac{n-k}{n}\biggr)}^{j}\\
E[Z] &= \frac{k}{n}\frac{1}{{(1-\frac{n-k}{n})}^2}\\
E[Z] &= \frac{k}{n}\frac{1}{{(\frac{k}{n})}^2}\\
E[Z] &= \frac{n}{k}
\end{align}
Again, this is to be expected. 

	\item[d.] In order to determine the expected number of indices picked until the entire array has been searched, define the following variables. Let $Z$ be a random variable such that $Z$ equals the number of indices picked until the entire array has been searched. Let $Y_i$ equal the number of indices picked since the $i$-th indice was found and until the $(i+1)$-th indice is found. Therefore,
\begin{align}
Z &= Y_0 + Y_1 + Y_2 + \cdots + Y_{n-1}\\
E[Z] &= E[Y_0 + Y_1 + Y_2 + \cdots + Y_{n-1}]\\
E[Z] &= E[Y_0] + E[Y_1] + E[Y_2] + \cdots + E[Y_{n-1}]
\end{align}
We can calculate the E[$Y_i$] directly. Remember that $Y_i$ is the number of tries to find the $(i+1)$-th indice after we have already found $i$ indices:
\begin{align}
E[Y_i] &= 1\cdot{Pr[Y_i=1]} + 2\cdot{Pr[Y_i=2]} + 3\cdot{Pr[Y_i=3]} + \cdots\\
E[Y_i] &= 1\cdot{\frac{n-i}{n}}+2\cdot{\frac{i}{n}}\cdot{\frac{n-i}{n}}+3\cdot{{\biggl(\frac{i}{n}\biggr)}^2}\cdot{\frac{n-i}{n}}+\cdots\\
E[Y_i] &= \frac{n-i}{n}(1 + 2\cdot{\frac{i}{n}} + 3\cdot{{\biggl(\frac{i}{n}\biggr)}^2} + \cdots)\\
E[Y_i] &= \frac{n-i}{n}\sum_{j=0}^{\infty}(j+1){\biggl(\frac{i}{n}\biggr)}^{j}\\
E[Y_i] &= \frac{n-i}{n}\frac{1}{{(1-\frac{i}{n})}^2}\\
E[Y_i] &= \frac{n-i}{n}\frac{1}{{(\frac{n-i}{n})}^2}\\
E[Y_i] &= \frac{n}{n-i}
\end{align}
Now we can calculate the E[$Z$]. However, a closed form of this particular solution is not known to me at this time and so I will leave it in the unsimplified form:
\begin{align}
E[Z] &= \sum_{i=1}^{n-1}{\frac{n}{n-i}}
\end{align}
\end{itemize}

\end{document}