CPS 1 (Ramm)			Spring 1995		         19 April 1995

				 Quiz #12
Name _______________________					Section _____

A. Say that a program's execution time behavior can be expressed by

         2
t = C * N

where t is the execution time, C is some constant, and N is the number of
data objects dealt with.

If the program takes 3 seconds to deal with 200 objects, how much time
should it take to deal with 400 objects?

                                              -------

B. Say that we run another program for several different amounts of data
(represented by N) and get the following timing results:

N	t
-----------
10	13 s
20	26 s
30	39 s
40	52 s

Give the formula that describes the execution time behavior.


	t = _____________________

What will the time be for N = 100?
                                    ----------


C. Assume we have yet another program which we run for several small values
of N.  We notice that every time we increase N by one, it takes 10 times
as long to run.  Circle those of the following terms that we might reasonably
use to describe the behavior of the program and it's underlying algorithm.

polynomial	exponential	intractable	logarithmic

	difficult-for-computers		made-for-computers	



D. Assume the information in a telephone book has been placed in a computer
memory, alphabetized like in a real phone book.  Which algorithmic behavior
could we expect from a well written search program using a binary search?
(N is the number of entries in the phone book.)

	1)  Logarithmic time (t = C * log N)

	                             2
	2)  Quadratic time (t = C * N )


	3)  Linear time (t = C * N)