HW03: Analysis of Algorithm Complexity due Wed 13 Sep 10:00

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. 
    power(x,n)
   // input: $x$ is a number and $n$ is a non-negative integer
   // output: $x^n$
   if $n=0$ then
      return $1$
   if $n$ is odd then
      y $\leftarrow$ power($x,(n-1)/2$)
      return $x \cdot y \cdot y$
   else
      y $\leftarrow$ power($x,n/2$)
      return $y \cdot y$

    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.
    $\displaystyle \begin{array}{ccc} 4n \log n+2n & 2^{10} & 2^{\log n} \\ 3n+100\log n & 4n & 2^n \\ n^2+10n & n^3 & n \log n \end{array} $

  5. (2 pts) Analyze the running time for the following algorithm. Express your answer using big-oh notation in terms of the input $n$. 
    fun1($A,n$)
   // input: $A$ is an array with $n \geq 1$ integers
   // output: the sum of elements at even-numbered indices in $A$
   $s \leftarrow A[0]$
   for $i \leftarrow 2$ to $n-1$ by increments of 2 do
      $s \leftarrow s + A[i]$
   return $s$

  6. (2 pts) Analyze the running time for the following algorithm. Express your answer using big-oh notation in terms of the input $n$. 
    fun2($A,n$)
   // input: $A$ is an array with $n \geq 1$ integers
   // output: the sum of the prefix sums in $A$
   $s \leftarrow A[0]$
   for $i \leftarrow 0$ to $n-1$ do
      $s \leftarrow s + A[0]$
      for $j \leftarrow 1$ to $i$ do
         $s \leftarrow s + A[j]$
   return $s$

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

Data Structures

Course Resources

Grades and Homework

Quick Links