Analysis of Algorithm Complexity due Wed 14 Sep 14:30

Work the following problems, some of which are borrowed from the book Data Structures and Algorithms in Java, 5th edition by Goodrich and Tamassia.

To receive full credit you will need to show your work. Final answers should be clearly marked. Write only on the front of a page. Staple multiple pages. All work should be legible.

  1. (4 pts) Implement the following algorithm in Java. \begin{lstlisting}[mathescape,columns=fullflexible,basicstyle=\fontfamily{lmvtt}...
...t y$
else
y $\leftarrow$\ power($x,n/2$)
return $y \cdot y$
\end{lstlisting}

    You may attach a printout of your working program to the rest of your hand-written work.

  2. (2 pts) Trace the algorithm given in problem 1 if the initial call is power(2,9). Use the same notation for tracing recursive algorithms we used in class.

  3. (2 pts) Suppose the number of operations executed by algorithm $A$ is $40n^2$ and the number of operations executed by algorithm $B$ is $2n^3$. Determine $n_0$ such that $A$ is better than $B$ for $n \geq
n_0$.

  4. (4 pts) Order the following functions by asymptotic growth rate from slowest growing to fastest growing.

    \begin{displaymath}
\begin{array}{ccc}
4n \log n+2n & 2^{10} & 2^{\log n} \\
...
...00\log n & 4n & 2^n \\
n^2+10n & n^3 & n \log n
\end{array} \end{displaymath}

  5. (2 pts) Analyze the running time for the following algorithm. Express your answer using big-oh notation in terms of the input $n$. \begin{lstlisting}[mathescape,columns=fullflexible,basicstyle=\fontfamily{lmvtt}...
...1$\ by increments of 2 do
$s \leftarrow s + A[i]$
return $s$
\end{lstlisting}

  6. (2 pts) Analyze the running time for the following algorithm. Express your answer using big-oh notation in terms of the input $n$. \begin{lstlisting}[mathescape,columns=fullflexible,basicstyle=\fontfamily{lmvtt}...
...\leftarrow 1$\ to $i$\ do
$s \leftarrow s + A[j]$
return $s$
\end{lstlisting}

  7. (2 pts) Show that $(n+1)^5 \in \Theta(n^5)$.

  8. (2 pts) Show that $n \in O(n \log n)$.

  9. (3 pts) Show that $x^2+4x+17$ is in $O(x^2)$ but that $x^3$ is not in $O(x^2)$

  10. (3 pts) Give a good big-O estimate for these functions:
    1. $(n^2+8)(n+1)$
    2. $(n \log n+n^2)(n^3+2)$
    3. $(n!+2^n)(n^3+log(n^2+1))$

Quick Links