\documentclass[11pt]{article}


\begin{document}

\title{{\bf CS 240 Data Structures and Algorithms
\\
Fall 2015
\\
Homework $\# 2$: Asymptotic Analysis
}}

% Uncomment \author and put your name in it
%\author{}

\maketitle



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.

\section{Analyze C Algorithms (9 pts.
total)}\label{analyze-c-algorithms-9-pts.-total}

Analyze the running time of each of the following three C functions.
Each of the functions takes as input an integer array \texttt{arr} and
its length \texttt{n}. For each function you should give the running
time $T(n)$ as a function of $n$ and then give the appropriate Big-O
classification. (3 pts. each)

NOTE: For the purposes of this problem, integer addition and
multiplication are the \emph{only} basic operation that you should count
when determining the running time $T(n)$ (i.e.~you can ignore array
accesses, assignments, etc.). You can assume for simplicity that $n$
is divisible by 2.


\begin{verbatim}
	
int A(int arr[], int n) 
{
    int result = 25;

    int i = n;
    while (i > 1) {
        for (int j = 0; j < n; j++) {
            result += 1;
            result += 3 * arr[j];
        }
        i = i / 2;
    }
    
    return result;
}

int B(int arr[], int n) 
{
    int result = 0;
    
    for (int i = 0; i < n/2; i++) {
        result += 3 * arr[i];
    }
    
    for (int i = n/2; i < n; i++) {
        result += 4 * arr[i];
    }
    
    for (int i = n-1; i >= 0; i--) {
        result += 3 * arr[i];
        result += 5 * arr[i];
    }
    
    return result;

}

int C(int arr[], int n)
{
    int result = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 5; j++) {
            for (int k = 0; k < n; k++) {
                result += j * j + arr[k];
            }
        }
    }
    return result;
}
	
\end{verbatim}


\section{Comparing Functions (14 pts.
total)}\label{comparing-functions-14-pts.-total}

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 each)

\begin{tabular}{|l||c|c|c|}
\hline
Pr. & $f(n)$ & $g(n)$ & $f(n)$ is ?? $(g(n))$ \\
\hline
a) & $.00001n^4$ & $375 \log_2 n$ & \\
b) & $24 n$ & $2n^2 + 1$ & \\
c) & $ 3n^3 + 2n $ & $2^n$ & \\
d) & $6n$ & $\log_2 n$ & \\
e) & $n!$ & $5 n^{20} + n^2 \log_2 n$ & \\
f) & $3n$ & $3 \log_2 (2^n)$ & \\
g) & $95 n + 2$ & $3 n + \log_2 n$ & \\
\hline
\end{tabular}


\section{Orders of Functions (14 pts.
total)}\label{orders-of-functions-14-pts.-total}

List each of the functions from \#2 from slowest to fastest growing in a
table like the table below. Group the functions by complexity class.
Indicate which functions are in the same complexity class (same
big-$\Theta$).

\vspace{14pt}
\begin{tabular}{|l|c|}
  \hline
  Complexity class & Functions from 2. in class \\
  \hline
  & \\
  \hline
  & \\
  \hline
  & \\
  \hline
  & \\
  \hline
  & \\
  \hline
  & \\
  \hline
  & \\
  \hline
\end{tabular}

NOTE: You may need fewer rows than provided.

\section{Comparing algorithms. (1
pt.)}\label{comparing-algorithms.-1-pt.}

Consider the following two algorithms: Algorithm A requires $8n+24$
steps to copmlete on an input of size $n$. Algorithm B requires
$2n^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.

\section{Proof of Big-$\Theta$ (2
pts.)}\label{proof-of-big-theta-2-pts.}

Using either definition of Big-$\Theta$, demonstrate that
$3 n^4 + 2 n^2 + 3$ is $\Theta(n^4)$.

\end{document}