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


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

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

Answers to the following exercises should be submitted through Canvas as
.pdf files.  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}
