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


\begin{document}
\newcommand{\bq}{\item \begin{samepage} }
  \newcommand{\eq}{\end{samepage}}
\maketitle

Answers to the following exercises should be prepared in a text editor
and submitted through blackboard as .pdf files.  Equations should be
properly formatted using equation editing software.


\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.
Addition should be used as the basic operation.  For each function
provide both the exact growth rate and the appropriate big-O
class. (12pts)
\begin{verbatim}
def someFunc1(values):
    sum = 0
    for i in range(len(values)):
        sum += 2 * i
    for val in values:
        sum += 4 * val
    return sum
\end{verbatim}

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

\begin{verbatim}
def someFunc3(values):
    sum = 0
    i = len(values)
    while i > 1:
        sum += 1
        sum += i 
        i = i/2
    return sum
\end{verbatim}
\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.  (7pts)

\begin{tabular}{|l|l|l|l|}
\hline 
 & $f(n)$ & $g(n)$ & $f(n) \in ??(g(n))$\\ 
\hline 
a) & $10n - 2$ & $2n$& \\ 
\hline 
b) & $n!$ & $2^n$ &\\ 
\hline 
c) & $.01n^3$ & $120n^2 + 1000n$ &\\ 
\hline 
d) & $n$ & $\log_2 n$ &\\ 
\hline 
e) & $4n$ & $n^2$ &\\ 
\hline 
f) & $n^2\log_2 n$ & $n^2 + n\log_2 n$ &\\ 
\hline 
g) & $\log_2(2^n)$ & $n$ &\\ 
\hline 
\end{tabular} 
\eq

\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$). (4pts) \eq

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

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

\end{enumerate}

\end{document}
