CS410, Summer 1998
Quiz #10
July 28

Consult no sources.				Name:

1. What is the worst-case running time for quicksort?  How could it occur?

2. What is the definition of a lower-bound for an algorithm?

3. What is the definition of a lower-bound for a problem?

4. How many permutations are there of n objects?

ANSWERS
=======

1. O(n^2) If we always choose the minimum (or maximum) element in a
range as our pivot element.

2. A (time) lower bound for an _algorithm_ is a running time such that
for all inputs, the algorithm takes at least that much time.  That is,
it is just a lower bound on the best-case running time of the algorithm.

3. A (time) lower bound for a _problem_ is a running time such that for
all algorithms, there is some input such that the algorithm on that
input takes at least that much time.  That is, it means no algorithm
can do better than the lower bound for all inputs.

4. n!