# Problems for Session A3: Analyzing Algorithms

### Problem A3-A: Plotting exponentiation

Determine the wall-clock time it takes to compute 1.3N recursively for every n between 0 and 100. (Note that you'll need to be careful to measure only the time of execution.) Plot the points. Is the curve smooth? If not, suggest why not.

### Problem A3-B: Comparing exponentiation

Determine the wall-clock time it takes to compute 1.0011024 recursively. Determine the wall-clock time it takes to compute 1.001511 iteratively. Which is quicker? Why?

### Problem A3-C: Plotting exponentiation, revisited

Determine the number of steps used to compute 1.3N recursively for every N between 0 and 100. Plot the points. Is the curve smooth? If not, suggest why not.

### Problem A3-D: Comparing exponentiation, revisited

Determine the number of steps it takes to compute 1.0011024 recursively. Determine the number of steps it takes to compute 1.001511. Explain the difference.

### Problem A3-E: Sorting

Note that we can use our modified `kSmallest` algorithm to sort arrays (i.e., put all of the elements in order). How? If there are n elements in the array, we ask to find the n smallest elements. Since the algorithm puts the n smallest elements in order, it has sorted the whole array.

Use this observation to add a `sort` method to `IntSeq` (and to `StringSeq`, if you developed it).

### Problem A3-F: Sorting, revisited

Find a textbook or Web page that discusses sorting and determine the name of the sorting algorithm we developed in problem A3-E.