% Search for all the places that say "PUT SOMETHING HERE".
\documentclass[11pt]{article}
\usepackage{amsmath,textcomp,amssymb,geometry,graphicx}
\def\Name{Andrew Szeto} % Your name
\def\Sec{105} % Your discussion section
\def\Login{cs170-ix} % Your login
\title{CS170--Spring 2012 --- Solutions to Homework 2}
\author{\Name, section \Sec, \texttt{\Login}}
\markboth{CS170--Spring 2012 Homework 2 \Name, section \Sec}{CS170--Spring 2012 Homework 1 \Name, section \Sec, \texttt{\Login}}
\pagestyle{myheadings}
\begin{document}
\maketitle
\begin{enumerate}
\item
\begin{enumerate}
\item For the recurrence $T(n) = 3T(n/2)+O(n)$, the general $k$th term is $3^kT(n/2^k)+kcn$ as an upper bound for $T(n)$. To get $T(1)$, we should set $k=\text{log}_2\,n$. Plugging it in gives us $T(n) \leq 3^{\text{log}_2\,n}T(1)+cn\,\text{log}_2\,n = O(3^{\text{log}\,n})$.
\item For the recurrence $T(n)=T(n-1) + O(1)$, we can say that the $O(1)$ step takes $c$ operations, and create an upper bound as follows:
\begin{align*}
T(n) & \leq T(n-1) + c\\
& \leq T(n-2) + 2c\\
& \leq T(n-2) + 3c\\
.\\
.\\
.\\
& \leq T(n-k) + kc
\end{align*}
Plugging in $k=n-1$ gives us $T(n) \leq T(1) + (n-1)c = O(n)$.
\end{enumerate}
\newpage
\item
Let the three recurrence relations be denoted as $T_A, T_B,$ and $T_C$, where $T_A(n) = 5T_A(n/2) + O(n)$, $T_B(n) = 2T_B(n-1) + O(1)$, and $T_C(n) = 9T_C(n/3) + O(n^2)$. We will analyze each algorithm separately.
\newpage
\item
\begin{enumerate}
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\end{enumerate}
\newpage
\item
PUT SOMETHING HERE
\newpage
\item
\begin{enumerate}
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\end{enumerate}
\newpage
\item
\begin{enumerate}
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\item
PUT SOMETHING HERE
\end{enumerate}
\end{enumerate}
\end{document}