This website is preserved for historical and scholarly reference and is no longer actively maintained.
Homework #7
Due Wednesday, October 14 at the beginning of class.
You are given a program that requires 4.0 sec. to run on 1000 data items.
#1. If the algorithm is O(N) and the number of data items is increased
to 5000, about how long do you expect the program to require? Show
your work.
#2. If the algorithm is O(N^2) and the number of data items is increased
to 5000, about how long do you expect the program to require? Show
your work.
#3. If the algorithm is O(log N), where log refers to log base 2, and
the number of data items is increased to 5000, about how long do
you expect the program to require? Show your work.
#4. If the algorithm is O(N log N), where log refers to log base 2,
and the number of data items is increased to 5000, about how long
do you expect the program to require? Show your work.
#5. If the algorithm is O(2^N) and the number of data items is
increased to 5000, about how long do you expect the program to
require? You should express your answer in mathematical form,
but it is not necessary to simplify your answer to a simple
real number.