Determine the wall-clock time it takes to compute 1.3^{N}
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.

Determine the wall-clock time it takes to compute 1.001^{1024}
recursively. Determine the wall-clock time it takes to compute
1.001^{511} iteratively. Which is quicker? Why?

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

Determine the number of steps it takes to compute 1.001^{1024}
recursively. Determine the number of steps it takes to compute
1.001^{511}. Explain the difference.

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

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

[Front Door] [Introduction] [Code]

Copyright (c) 1998 Samuel A. Rebelsky. All rights reserved.

Source text last modified Mon Oct 25 22:18:46 1999.

This page generated on Tue Oct 26 15:38:07 1999 by Siteweaver.

Contact our webmaster at rebelsky@math.grin.edu