<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[11pt]{article}
\usepackage[margin=1in]{geometry}

\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 file (preferably PDF). 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 &gt; 1) {
        for (int j = 0; j &lt; n; j++) {
            result += 1;
            result += 3 * arr[j];
        }
        i = i / 2;
    }
    
    return result;
}

\end{verbatim}

\newpage

\begin{verbatim}

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

}

\end{verbatim}


\begin{verbatim}

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

\newpage

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

\vspace{1cm}

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

\vspace{1cm}

\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 &amp; Functions from 2. in class \\
  \hline
  &amp; \\
  \hline
  &amp; \\
  \hline
  &amp; \\
  \hline
  &amp; \\
  \hline
  &amp; \\
  \hline
  &amp; \\
  \hline
  &amp; \\
  \hline
\end{tabular}

NOTE: You may need fewer rows than provided.

\newpage

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

Consider the following two algorithms: Algorithm A requires $8n+24$
steps to complete 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.

\vspace{3cm}

\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}
</pre></body></html>