\documentclass[10pt,letterpaper]{article}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{multirow}
\usepackage{graphicx}
\usepackage{color}
\title{
        CS240 HW \#02 
}
\author{}
\date{}


\begin{document}
\newcommand{\bq}{\item \begin{samepage} }
  \newcommand{\eq}{\end{samepage}}
\vspace*{-.7in}

\begin{center}
\Large{CS240 Homework 2}
\end{center}

\begin{center}
\textcolor{red}{\textbf{DUE Friday, Sept 19 at 14:30 (2:30pm)}}
\end{center}

Your answers to the following exercises should be submitted through Canvas as a
single \texttt{hw02.pdf} file.  Equations should be properly formatted using
equation editing software, such as LaTeX or the equation editor in MS Word or
LibreOffice.


\begin{enumerate}


\bq Analyze each of the following three Python functions.  In each case you may
assume that \textbf{\texttt{values}} is a list of integers. The length of
values should be used as the input size ($n$).  For each function provide both
the exact growth rate and the appropriate big-O class. (3pts)

NOTE: Integer addition is the \emph{only} basic operation that you should count
when determining the exact operation counts and growth rates for this question.

\begin{verbatim}
def someFunc1(values):
    sum = 0
    for i in range(len(values)):
        sum += i
    for val in values:
        sum += 4 * val
        sum += 8 * val
    return sum
\end{verbatim}

%ANSWER FOR Q1.1 GOES HERE

\begin{verbatim}
def someFunc2(values):
    sum = 0
    for i in values:
        for j in values:
            sum += 2 * j
            for k in range(5):
                sum += k * k
    return sum
\end{verbatim}

%ANSWER FOR Q1.2 GOES HERE

\begin{verbatim}
def someFunc3(values):
    sum = 0
    for i in values:
        j = len(values)
        while j > 1:
            sum += 1
            sum += i 
            j = j/2
    return sum
\end{verbatim}

%ANSWER FOR Q1.3 GOES HERE

\pagebreak

\eq

\bq For the following pairs of functions, indicate whether the ?? could be
replaced with $O$, $\Omega$ or $\Theta$.  More than one may be correct: indicate
all that apply.  (2pts)

\begin{tabular}{|l|l|l|l|}
\hline 
 & $f(n)$ & $g(n)$ & $f(n) \in ~??(g(n))$\\ 

% ANSWERS FOR Q2 GO IN THIS TABLE:

\hline 
a) & $2n$ & $n^2$                  &                          \\ 
\hline 
b) & $n$ & $\log_2 n$              &                          \\ 
\hline 
c) & $.001n^3$ & $100n^2 + 1000n$  &                          \\ 
\hline 
d) & $n^2$ & $2^n$                 &                          \\ 
\hline 
e) & $5n$ & $8n+1$                 &                          \\ 
\hline 
f) & $n!$ & $n^4 + 10n^2\log_2 n$  &                          \\ 
\hline 
g) & $n$ & $\log_2(2^n)$           &                          \\ 
\hline 
\end{tabular} 
\eq

\vspace{20px}

\bq List each of the functions from the table above from slowest to
fastest growing.  Indicate which functions are in the same complexity
class (same big-$\Theta$). (2pts)


\begin{tabular}{|l|l|}
\hline
Complexity Class  & Functions from slowest to fastest growing\\

% ANSWERS FOR Q3 GO IN THIS TABLE:

\hline
                  &                                          \\[25px]
\hline
                  &                                          \\[25px]
\hline
                  &                                          \\[25px]
\hline
                  &                                          \\[25px]
\hline
                  &                                          \\[25px]
\hline
                  &                                          \\[25px]
\hline
                  &                                          \\[25px]
\hline
                  &                                          \\[25px]

\hline

\end{tabular} 

NOTE: You may need fewer rows than provided.


 \eq

\newpage

\bq Consider the following two algorithms: Algorithm A requires $3n + 4$ steps
to complete on an input of size $n$.  Algorithm B requires $n^2$ steps.  For
what values of $n$ should we prefer algorithm A?  For what values of $n$ should
we prefer algorithm B? Justify your answer. (1pt)
\eq


% ANSWER FOR Q4 GOES HERE



\bq Using either definition of big-$\Theta$, demonstrate that
$n^3 + 2n^2 + 3n \in \Theta(n^3)$  (2pts)
\eq


% ANSWER FOR Q5 GOES HERE






\end{enumerate}

\end{document}
