CSC 349 Scribe Notes

scribe-notes-2021-09-24.tex

\title{CSC 349 - Recurrence Relations}
\author{Astrid Yu}
\date{September 24, 2021}

\documentclass{article}

\usepackage[margin=1in]{geometry}
\usepackage{multicol}
\usepackage{hyperref}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{tikz}
\usepackage{prooftrees}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{outlines}
\usepackage[makeroom]{cancel}

% workaround for prooftrees
\newcommand{\eq}{=}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}

\forestset{
	not line numbering
}

\begin{document}
\maketitle
\tableofcontents

\section{Review from Wednesday, and wrap-up of the proof}

On Wednesday, we defined Binary Search (see Algorithm \ref{alg:binarysearch} if it falls off the page).

\begin{algorithm}[H]
\caption{BinarySearch($A$, $x$, min, max)}
\label{alg:binarysearch}
\KwIn{A sorted list of integers $A = \{a_1, a_2, \dots, a_n\}$, and indices $p$ and $q$. Initially, $p = 1$ and $q = n$.}
\KwOut{The index $i$ for some $p \leq i \leq q$ such that $a_i = i$, or $-1$ if $i$ $i$ does not exist.}
\uIf{$\max < \min$}{
	\Return{$-1$}\;
}
\uElse{
	\If{$x < A[\lfloor (\max + \min) / 2 \rfloor]$}{
		\Return{BinarySearch($A$, $x$, $\min$, $\lfloor (\max + \min) / 2 \rfloor - 1$)}\;
	}
	\If{$x > A[\lfloor (\max + \min) / 2 \rfloor]$}{
		\Return{BinarySearch($A$, $x$, $\lfloor (\max + \min) / 2 \rfloor + 1$, $\max$)}\;
	}
	\Return $\lfloor (\max + \min) / 2 \rfloor$\;
}
\end{algorithm}

Then, we proved the following lemma about Binary Search using induction:

\begin{lemma}
	If $x \in A[\min, \max]$ and $\max - \min + 1 = n$, then BinarySearch returns $i$ such that $x = A[i]$.
\end{lemma}

From this lemma, we have a corollary:
\begin{corollary}
	If $x \in A$, then BinarySearch returns $i$ such that $x = A[i]$.
\end{corollary}

We can prove another lemma:
\begin{lemma}
	If $x \notin A$ then BinarySearch returns $-1$.
	\begin{proof}
		By way of contradiction, suppose $x \notin A$ and BinarySearch does not return $-1$. However, the only place that happens is on line 5, which requires $A[mid] = x$. This cannot happen because $x \notin A$, so there is a contradiction.
	\end{proof}
\end{lemma}

With the 2 lemmas, we can prove our theorem:
\begin{theorem}
	BinarySearch is correct.
\end{theorem}

\section{Calculating running time using the Tree Method}

We can define a recurrence relation for our running time:

$$T(n) = T\left(\frac{n}{2}\right) + O(1)$$

Essentially, what this says is:
\begin{itemize}
	\item we recurse once (since the coefficient on $T\left(\frac{n}{2}\right) $ is 1)
	\item we reduce our search size by $\frac{n}{2}$ at every step
	\item it takes $O(1)$ to perform this reduction.
\end{itemize} 

The master theorem\footnote{\href{https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)}{Master theorem on Wikipedia}} can be used, but it's hard to remember. Thus, we will be using the tree method in this class. 

\textbf{NOTE:} Partial credit won't be given if you incorrectly use the master theorem on tests.

\subsection{Example 1}

To use the tree method, you draw out the recursion tree on the left, then write out how much work is done at that level of the tree. First, let's draw out the recursion tree:
\begin{center}
\begin{prooftree}
	{
		single branches=true
	}
	[n
		[\frac{n}{2}
			[\frac{n}{4}
				[\frac{n}{8}
					[\frac{n}{16}
						[\vdots
							[1]
						]
					]
				]
			]
		]
	]
\end{prooftree}
\end{center}

This tree happens to be a line. That's because we only recurse one time. We can count there to be $\log_2 n$ levels, since $n$ halves every time until we get to 1. Next, let's add the amount of work per level next to it:

\begin{center}
	\begin{prooftree}
		{
			single branches=true
		}
		[n, just=$1$
			[\frac{n}{2}, just=$1$
				[\frac{n}{4}, just=$1$
					[\frac{n}{8}, just=$1$
						[\frac{n}{16}, just=$1$
							[\vdots, just=$\vdots$
								[1, just=$1$
								]
							]
						]
					]
				]
			]
		]
	\end{prooftree}
\end{center}

Since the second term is $O(1)$, we have $1$ for each level. Since there are $\log_2 n$ levels, and $1$ per level, we add them all together to get

$$(\log_2 n) (1) = \log_2 n$$

work. Thus, our algorithm is $O(\log n)$.\footnote{We can remove the base from our log because changing a log's base is equivalent to multiplying by a constant, due to the \href{https://www.khanacademy.org/math/algebra2/x2ec2f6f830c9fb89:logs/x2ec2f6f830c9fb89:change-of-base/a/logarithm-change-of-base-rule-intro}{Logarithm power change rule.}}

\textbf{NOTE:} This is NOT simply multiplying a value by tree height. We are actually adding $\log_2 n$ instances of $1$ together. The amount of work at each level is not always constant. This distinction can be seen in Example \ref{ex3}.

\subsection{Example 2}

Merge sort has a recurrence relation of 

$$T(n) = 2T \left( \frac{n}{2} \right) + O(n)$$

Note that there is a coefficient of $2$ in front of our recursion. We will draw out our tree like so:

\begin{center}
\begin{prooftree}
	{
		single branches=true
	}
	[n, just=$n$
		[\frac{n}{2}, just=$\frac{n}{2} + \frac{n}{2} \eq n$
			[\frac{n}{4}, just=$\frac{n}{4} + \frac{n}{4} + \frac{n}{4} + \frac{n}{4} \eq n$
				[\frac{n}{8}, just=$8 \left( \frac{n}{8} \right) \eq n$
					[\vdots, just=$\vdots$
						[1, just=$n \cdot 1 \eq 1$]
						[\cdots]
					]
				]
				[\frac{n}{8} [\vdots]]
			]
			[\frac{n}{4}
				[\frac{n}{8} [\vdots]]
				[\frac{n}{8} [\vdots]]
			]
		]
		[\frac{n}{2}
			[\frac{n}{4}
				[\frac{n}{8} [\vdots]]
				[\frac{n}{8} [\vdots]]
			]
			[\frac{n}{4}
				[\frac{n}{8} [\vdots]]
				[\frac{n}{8} [\vdots]]
			]
		]
	]
\end{prooftree}
\end{center}

You can see the pattern: at every level, it is $n$ work. Again, there are $\log_2 n$ levels. Therefore, merge sort is $O(n \log n)$.

\subsection{Example 3}
\label{ex3}

Consider

$$T(n) = T(\frac{n}{2}) + O(n^2)$$

The recursion tree is as follows:

\begin{center}
	\begin{prooftree}
		{
			single branches=true
		}
		[n, just=$n^2$
		[\frac{n}{2}, just=$2\left(\frac{n}{2}\right)^2 \eq \frac{n^2}{2}$
		[\frac{n}{4}, just=$4\left(\frac{n}{4}\right)^2 \eq \frac{n^2}{4}$
		[\frac{n}{8}, just=$8\left(\frac{n}{8}\right)^2 \eq \frac{n^2}{8}$
		[\vdots, just=$\vdots$
		[1, just=???]
		[\cdots]
		]
		]
		[\frac{n}{8} [\vdots]]
		]
		[\frac{n}{4}
		[\frac{n}{8} [\vdots]]
		[\frac{n}{8} [\vdots]]
		]
		]
		[\frac{n}{2}
		[\frac{n}{4}
		[\frac{n}{8} [\vdots]]
		[\frac{n}{8} [\vdots]]
		]
		[\frac{n}{4}
		[\frac{n}{8} [\vdots]]
		[\frac{n}{8} [\vdots]]
		]
		]
		]
	\end{prooftree}
\end{center}

What is the value at the $i$-th row? Following the pattern, it is:
\begin{align*}
	2^i \left( \frac{n}{2^i} \right)^2 &= 2^i \left( \frac{n^2}{2^2i} \right) \\
	&= \frac{n^2}{2^i}
\end{align*}

There are $\log_2 n$ rows, so the amount of work at the last row is

\begin{align*}
	\frac{n^2}{2^i} &= \frac{n^2}{2^{\log_2 n}} = \frac{n^2}{n} \\
	&= n
\end{align*}

Writing the total work as a sum, we have

$$n^2 + \frac{n^2}{2^1} + \frac{n^2}{2^2} + \frac{n^2}{2^3} + \cdots + \frac{n^2}{n}$$

We can factor out $n^2$:

$$n^2 + n^2 \left( \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^3} + \cdots + \frac{1}{n} \right)$$

This is a finite geometric series. To evaluate the second term, we could technically use the formula for geometric series,\footnote{\href{https://www.purplemath.com/modules/series5.htm}{see the formulas on PurpleMath}} but intuitively, we can see that the series approaches $1$, but is strictly less than $1$, no matter what $n$ is provided.

So, $n^2$ added to some fraction of $n^2$ less than 1 will always be $< 2n^2$. Thus, we can say $T$ is $O(n^2)$.

\subsection{Example 4}

Consider

$$T(n) = T(\frac{n}{2}) + O(1)$$

The recursion tree is as follows:

\begin{center}
	\begin{prooftree}
		{
			single branches=true
		}
		[n, just=$1$
		[\frac{n}{2}, just=$1 + 1 \eq 2$
		[\frac{n}{4}, just=$1 + 1 + 1 + 1 \eq 4$
		[\frac{n}{8}, just=$8(1) \eq 8$
		[\vdots, just=$\vdots$
		[1, just=$n$]
		[\cdots]
		]
		]
		[\frac{n}{8} [\vdots]]
		]
		[\frac{n}{4}
		[\frac{n}{8} [\vdots]]
		[\frac{n}{8} [\vdots]]
		]
		]
		[\frac{n}{2}
		[\frac{n}{4}
		[\frac{n}{8} [\vdots]]
		[\frac{n}{8} [\vdots]]
		]
		[\frac{n}{4}
		[\frac{n}{8} [\vdots]]
		[\frac{n}{8} [\vdots]]
		]
		]
		]
	\end{prooftree}
\end{center}

Once again, we can write the summed work as a geometric series. It's more useful to write them from bottom to top in this case:

\begin{align*}
&n + \frac{n}{2} + \frac{n}{4} + \cdots + 8 + 4 + 2 + 1 \\
&= n + \frac{n}{2^1} + \frac{n}{2^2} + \cdots + \frac{n}{\frac{n}{2}} + \frac{n}{n} \\
&= n + n \left(\frac{1}{2^1} + \frac{1}{2^1} + \frac{1}{2^2} + \cdots \right)
\end{align*}

Once again, this is a finite geometric series that approaches $1$.

So, $n$ added to some amount of $n$ less than 1 will always be $< 2n$. Thus, we can say $T$ is $O(n)$.

\subsection{Example 5}
This is a relation that the master method won't work on:

$$T(n) = T(n - 1) + O(1)$$

Drawing out the tree, on the left we have the tree of reductions and on the right we have the amount of work at each level.
\begin{center}
	\begin{prooftree}
		{
			single branches=true
		}
		[n, just=$1$
		[n - 1, just=$1$
		[n - 2, just=$1$
		[n - 3, just=$1$
		[n - 4, just=$1$
		[\vdots, just=$\vdots$
		[1, just=$1$
		]
		]
		]
		]
		]
		]
		]
	\end{prooftree}
\end{center}

This time, there are $n$ levels, and we add $1$ for each level. Therefore, the sum of the work on the right is $n$.

Thus, this is $O(n)$.

\subsection{Example 6}
Last one! The master theorem won't work on this one either:

$$T(n) = T(n - 1) + O(n)$$

Drawing out the tree, on the left we have the tree of reductions and on the right we have the amount of work at each level.
\begin{center}
	\begin{prooftree}
		{
			single branches=true
		}
		[n, just=$n$
		[n - 1, just=$n - 1$
		[n - 2, just=$n - 2$
		[n - 3, just=$n - 3$
		[n - 4, just=$n - 4$
		[\vdots, just=$\vdots$
		[1, just=$1$
		]
		]
		]
		]
		]
		]
		]
	\end{prooftree}
\end{center}

The sum can be written out as follows:
$$n + (n - 1) + (n - 2) + \cdots + (n - (n - 2)) + (n - (n - 1))$$

We can cancel out terms:
\begin{align*}
	&n + \cancel{(n - 1)} + \cancel{(n - 2)} + \cdots + (n - \cancel{(n - 2)}) + (n - \cancel{(n - 1)}) \\
	&= \underbrace{n + 0 + 0 + }_{\frac{n}{2}} \cdots \underbrace{+ n + n}_{\frac{n}{2}}
\end{align*}

Thus, the total work is $\left(\frac{n}{2}\right)(n)$, meaning $T$ is in $O(n^2)$.

\section{Hagoromo Bungu Chalk}

\begin{itemize}
	\item \href{https://en.wikipedia.org/wiki/Hagoromo_Bungu}{Wikipedia}
	\item \href{https://www.youtube.com/watch?v=PhNUjg9X4g8}{A YouTube video about the shortage},
	\item\href{https://www.amazon.com/stores/HAGOROMO/page/973F25F9-9AC8-488F-965C-E5F1DEFB2A4A}{Amazon page}
\end{itemize}

\end{document}