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.

- (4 pts) Implement the following algorithm in Java.
You may attach a printout of your working program to the rest of your hand-written work.

- (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. - (2 pts) Suppose the number of operations executed by algorithm
is and the number of operations executed by algorithm is
. Determine such that is better than for .
- (4 pts) Order the following functions by asymptotic growth rate
from slowest growing to fastest growing.

- (2 pts) Analyze the running time for the following algorithm.
Express your answer using big-oh notation in terms of the input .
- (2 pts) Analyze the running time for the following algorithm. Express your
answer using big-oh notation in terms of the input .
- (2 pts) Show that
.
- (2 pts) Show that
.
- (3 pts) Show that is in but that is not
in
- (3 pts) Give a good big-O estimate for these functions: